Meeting Rooms II

1. The obvious way

   Check every time point against all intervals: O(n²).

2. The key insight

   Sort by start. Keep a min-heap of end times of rooms in use. For each meeting: if the earliest end <= this start, that room is free, so pop it (reuse). Push this meeting's end. The heap size is the number of rooms in use; its largest size is the answer, which equals the final size.

3. The algorithm
   1. Sort meetings by start time.
   2. Min-heap of end times (rooms in use).
   3. Heap top <= this start? Pop it: reuse that room.
   4. Push this end. Answer: heap size at the end.

Watch it run

rooms busy until: 30

import heapq

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda meeting: meeting[0])        # by start time
    busy_until = []                                       # min-heap: when each room in use frees up
    for start, end in intervals:
        if busy_until and busy_until[0] <= start:
            heapq.heappop(busy_until)                     # that room is free: reuse it
        heapq.heappush(busy_until, end)
    return len(busy_until)

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.