Meeting Rooms II

Learning goal: Translate overlapping meeting intervals into a count of rooms.

Core idea A room is occupied for the entire duration of a meeting. Whenever several meetings are active simultaneously, each one needs a different room. Therefore, the minimum room count is the maximum number of active intervals at any instant.

Algorithm plan

• Read each interval as [start, end].
• Identify moments when meetings start and end.
• Track how many meetings are active after each event.
• Return the largest active count.

Micro-example For [0,30], [5,10], and [15,20], all three meetings overlap at time 15. The answer is at least 3, and three rooms are enough.

Pitfalls

• An ending meeting frees its room when end <= start for the next meeting.
• The input order does not describe the chronological order.
• Counting only total meetings misses the overlap pattern.

Recap

• The answer is a peak concurrency, not a sum of durations.
• Every simultaneous meeting consumes one room.

Learning goal: Understand why ongoing meeting end times are the right state to maintain.

Core idea Process meetings in increasing order of start time. A min-heap stores the end time of every meeting currently occupying a room. Its smallest value is the earliest room that could become available, so it is the only end time we need to inspect first.

Data structure model

• Heap contents: end times of meetings still using rooms.
• Heap root: smallest active end time.
• Heap size: rooms occupied after the current meeting is assigned.
• Maximum heap size: minimum rooms required.

Micro-example Before [18,25], the heap is [20,30], representing [15,20] and [0,30]. Since 20 > 18, neither room is free, so pushing 25 raises the heap size to 3.

Pitfalls

• Remove all ends <= start, not just one.
• Do not remove an end that is greater than the new start.
• Store end times, not whole intervals, because starts are already being processed.

Recap

• Sort starts to establish processing order.
• A min-heap exposes the earliest reusable room.
• The maximum heap size is the result.

Learning goal: Build the heap-based algorithm and justify its complexity.

Core idea Sort intervals by their start times. For each interval, remove every end time that is no later than its start; each removal represents reusing an available room. Then insert the current meeting's end time and update the maximum heap size.

Algorithm plan

1. Sort intervals by start.
2. Create an empty min-heap of end times.
3. For each [start, end], pop while heap[0] <= start.
4. Push end into the heap.
5. Return the largest heap size seen.

sort intervals by start
rooms = 0
for (start, end) in intervals:
    while heap is not empty and heap.min <= start:
        pop heap
    push end into heap
    rooms = max(rooms, heap.size)
return rooms

Micro-example Sorted input begins [0,30], [5,10], [15,20], [18,25], [25,35]. At start 18, the heap contains [20,30]; no end is available, so inserting 25 creates three active meetings.

Pitfalls

• Sorting by end time alone does not process arrivals correctly.
• The answer is not necessarily the final heap size; rooms may become free later.
• A comparison against every other interval creates an unnecessary O(n^2) algorithm.

Recap

• Sort by starts, remove reusable ends, then push the new end.
• Heap operations cost O(log n), giving total time O(n log n).

Learning goal: Trace every heap change on one concrete input.

Core idea Use the example [[0,30],[5,10],[15,20],[18,25],[25,35]], already listed above. The intervals are processed by start time. The heap shows exactly which rooms remain occupied, and its largest size records the peak overlap.

Heap trace

Micro-example At time 18, the end times 20 and 30 are both in the future. The new meeting cannot reuse either room, so the heap grows from 2 to 3.

Pitfalls

• Forgetting the second pop at start 25 leaves a stale meeting in the heap.
• Looking at the maximum end time would miss the earliest reusable room.

Recap

• The maximum heap size in this trace is 3.
• The final heap can be smaller than the answer.

Learning goal: Detect boundary errors and avoid the quadratic solution.

Core idea The heap method is efficient because it summarizes all active meetings using only their end times. The most important boundary rule is that end <= start means a room is available. The most common inefficient alternative compares each meeting with every other meeting, which costs O(n^2).

Algorithm plan

• Sort before scanning, even if input appears nearly ordered.
• Pop repeatedly, because several rooms may have ended.
• Push the current end after all reusable rooms are removed.
• Track the maximum size, not merely the final size.

Micro-example For [0,10] and [10,15], pop 10 before pushing 15; the answer is 1. For [0,10] and [9,15], do not pop; the answer is 2.

Pitfalls

• Using < start instead of <= start incorrectly treats touching meetings as overlapping.
• Popping only one ended meeting fails when multiple rooms are free.
• Returning the final heap size can undercount an earlier peak.

Recap

• Reuse all rooms whose end is at most the next start.
• Heap-based active tracking avoids pairwise comparisons.
• Test empty gaps, touching boundaries, nested intervals, and identical starts.

Learning goal: Analyze the solution and connect the implementation to the central invariant.

Core idea Sorting establishes chronological starts in O(n log n) time. Each meeting is pushed once and popped at most once; each heap operation costs O(log n). The heap may contain all meetings, so auxiliary space is O(n).

Algorithm plan

• Sort intervals by start.
• Maintain a min-heap of active end times.
• Remove every end <= start.
• Insert the current end and update the peak.
• Return the peak.

Micro-example For the walkthrough, the heap sizes are 1, 2, 2, 3, 2; the maximum is 3. The peak, not the last value, is the answer.

Pitfalls

• Do not claim O(n) time just because each interval is processed once; heap operations are logarithmic.
• Sorting the input in place may count as modifying the input, depending on the implementation.
• A two-pointer sweep over separately sorted starts and ends is also valid, with the same target complexity.

Recap

• Time: O(n log n).
• Space: O(n).
• Invariant: heap contents are the end times of active meetings.
• Result: maximum heap size is the minimum room count.