Meeting Rooms II

Meeting Rooms II asks: given a pile of meetings, how many rooms do you need so none of them collide? It is a classic interval problem, and the trick — the sweep line — turns a messy overlap question into a simple counting walk.

The slow way first

The obvious idea: for each meeting, count how many other meetings overlap it, and take the worst case. That is O(n²) — every meeting checked against every other. For a long calendar it is far too slow, and it does a lot of redundant comparing.

The question to ask: I do not actually care which meetings overlap — only how many are running at the same instant. The answer is the maximum number of meetings live at any moment, and there is a much cheaper way to find that peak.

The idea: sweep a line through time

Pull the start times and end times apart into two lists and sort each one. Now walk forward through time. Every time you pass a start, one more meeting is running, so add a room. Every time you pass an end, a meeting finished, so free a room. The peak room count you ever reach is the answer.

The key insight: a start and an end are just events on a timeline. We never need to match a specific start to its own end — we only count how many rooms are live, and remember the highest that count ever climbed.

Walk through it

Step through the animation. The s pointer walks the sorted starts, the e pointer walks the sorted ends. At each step we compare the next start with the next end: if the start is smaller a meeting opens (rooms goes up, and we update the peak); otherwise a meeting closes (rooms goes down). The two meetings overlapping at time 5 push the peak to 2, and nothing ever beats it — so the answer is 2.

Pseudocode

starts = the start times, sorted
ends   = the end times, sorted
rooms = 0, peak = 0
point s at the first start, e at the first end
while there are still starts to process:
    if next start < next end:
        rooms += 1                  # a meeting begins
        peak = max(peak, rooms)     # remember the worst overlap
        advance s
    else:
        rooms -= 1                  # a meeting ends, free a room
        advance e
return peak

The Python solution

def min_meeting_rooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)
    rooms = peak = 0
    s = e = 0
    while s < len(starts):
        if starts[s] < ends[e]:
            rooms += 1
            peak = max(peak, rooms)
            s += 1
        else:
            rooms -= 1
            e += 1
    return peak

• starts and ends are the two sorted event rows — we sort each independently, not as paired intervals.
• rooms is how many meetings are live right now; peak is the most we ever saw at once.
• The loop runs until every start is processed — once all meetings have opened, leftover ends can only lower rooms, never raise the peak.
• Lines 7-10 are the heart: if the next start beats the next end, open a room and bump the peak; otherwise close one.
• We never advance past the last start, so e never runs off the end of its row.

Complexity

Sorting the two rows costs O(n log n); the sweep itself is a single linear pass. We use O(n) extra space for the two sorted lists. The same sweep-line idea — split intervals into +1/−1 events and walk them in order — solves a whole family of overlap problems.

When this pattern shows up

Practice