📅 Interval Problems Made Simple

# Merge all overlapping time slots - perfect for calendar apps! def merge_intervals(intervals): """Like combining overlapping meetings into one big meeting""" if not intervals: return [] # Step 1: Sort by start time (earliest meeting first) intervals.sort(key=lambda x: x[0]) # Step 2: Start with the first interval merged = [intervals[0]] # Step 3: Check each interval for current in intervals[1:]: last_merged = merged[-1] if current[0] <= last_merged[1]: # They overlap! Extend the last merged interval merged[-1] = [last_merged[0], max(last_merged[1], current[1])] else: # No overlap, add as new interval merged.append(current) return merged # Example: Your busy day meetings = [[1,3], [2,6], [8,10], [15,18]] merged = merge_intervals(meetings) print(f"Your consolidated schedule: {merged}") # Output: [[1,6], [8,10], [15,18]] - Much cleaner! 🎉

# Check if one person can attend all meetings def can_attend_all_meetings(intervals): """Are you trying to be in two places at once?""" # Sort meetings by start time intervals.sort(key=lambda x: x[0]) # Check each pair of consecutive meetings for i in range(1, len(intervals)): if intervals[i][0] < intervals[i-1][1]: # Oops! This meeting starts before the previous one ends return False return True # You're good to go! ✅ # How many meeting rooms do we need? def min_meeting_rooms(intervals): """Like finding how many conference rooms to book""" if not intervals: return 0 # Separate start and end times starts = sorted([i[0] for i in intervals]) ends = sorted([i[1] for i in intervals]) rooms = 0 max_rooms = 0 s = e = 0 while s < len(starts): if starts[s] < ends[e]: # A meeting starts - need a room! rooms += 1 s += 1 else: # A meeting ends - room becomes free! rooms -= 1 e += 1 max_rooms = max(max_rooms, rooms) return max_rooms # Example: Company meetings meetings = [[0,30], [5,10], [15,20]] print(f"Rooms needed: {min_meeting_rooms(meetings)}") # Output: 2

# Find the skyline formed by buildings import heapq def get_skyline(buildings): """Each building: [left, right, height]""" events = [] # Create events for building starts and ends for left, right, height in buildings: events.append((left, -height, 'start')) # Negative for max heap events.append((right, height, 'end')) events.sort() result = [] heights = [0] # Ground level for x, h, event_type in events: if event_type == 'start': heapq.heappush(heights, h) else: heights.remove(-h) heapq.heapify(heights) # Check if max height changed max_height = -heights[0] if not result or result[-1][1] != max_height: result.append([x, max_height]) return result

class MyCalendarTwo: """Calendar allowing at most double booking""" def __init__(self): self.bookings = [] # All bookings self.overlaps = [] # Double-booked slots def book(self, start, end): # Check if it would cause triple booking for s, e in self.overlaps: if start < e and end > s: return False # Would be triple booked! # Add overlaps with existing bookings for s, e in self.bookings: if start < e and end > s: overlap_start = max(start, s) overlap_end = min(end, e) self.overlaps.append([overlap_start, overlap_end]) self.bookings.append([start, end]) return True # Usage example calendar = MyCalendarTwo() print(calendar.book(10, 20)) # True print(calendar.book(50, 60)) # True print(calendar.book(10, 40)) # True (double booking OK) print(calendar.book(5, 15)) # False (would be triple)