Pattern 4: Event sweep (rooms)

"How many meeting rooms do I need?" is the model question for a powerful technique: treat each start and each end as events on a timeline and sweep them in order, counting how many intervals are active at the same time.

Tried it? The number of rooms is how many meetings are happening at the same time at the worst instant. The theory below shows how to measure this "maximum overlap" without testing every instant.

The theory: starts and ends as events

The key idea: the minimum number of rooms is the maximum overlap at any point in time. To measure it, forget the intervals as blocks and think in events: each meeting contributes a +1 at its start (people arrive) and a -1 at its end (people leave). Sort all events by time and sweep, keeping a counter of "rooms in use" — the peak is the answer.

An elegant way (without building the list of events): sort the starts and the ends into two separate lists and use two pointers:

sorted starts, sorted ends
rooms = 0, max = 0, i = 0, j = 0
while there are starts:
    if start[i] < end[j]:      # one meeting started before another ended
        rooms += 1             # needs one more room
        i += 1
        max = max(max, rooms)
    else:                      # one meeting ended: frees a room
        rooms -= 1
        j += 1
return max

Each time a start happens before the next end, there's a new overlapping meeting → +1 room. When an end comes first, a room is freed. The largest value of rooms during the sweep is the minimum needed.

Endpoint convention: here we use start < end, so a meeting that ends exactly when another starts ([1,5] and [5,10]) frees the room in time — it doesn't count as overlap. Always check this rule in the problem statement.

The min-heap alternative

There's a second classic approach, which you'll see again in the Heap section: sort the meetings by start and keep a min-heap of the ends of the ongoing meetings. For each new meeting, if the smallest end in the heap has already passed, reuse the room (remove that end); otherwise, open a new room. The size of the heap is the number of rooms. Both approaches are O(n log n) — remember that "maximum overlap" has these two faces.

Sibling example: Meeting Rooms I

The simpler version asks only: can you attend all the meetings? (that is, does any of them overlap?). Just sort by start and check whether any meeting starts before the previous one ends:

Complexity

Both the event sweep and the min-heap are O(n log n) (dominated by the sort), with O(n) space. Meeting Rooms I is O(n log n) from the sort + O(n) in the scan. In all of them, the bottleneck is sorting — the rest is one pass.

Summary

• Minimum number of rooms = maximum overlap in time.
• Event sweep: starts (+1) and ends (−1) sorted; the peak of the counter is the answer. Alternative: min-heap of the ends (comes back in the Heap section).
• Meeting Rooms I: sort by start and detect any conflict.
• Everything is O(n log n), dominated by the sort.

Last stop: the synthesis of the Intervals section and the quiz before the exam.