Meeting Rooms II

This is the most asked interval question after Merge Intervals, and it joins this section to the heaps section. It has two standard solutions that look nothing alike and are, underneath, the same idea.

The problem

Given a list of meetings as [start, end], return the smallest number of rooms needed so that every meeting has a room and no room holds two meetings at the same time. A room freed at time 9 can host a meeting that starts at 9.

• [[2, 8], [3, 5], [6, 9], [9, 12], [4, 7]] → 3. At time 4, the meetings [2, 8], [3, 5] and [4, 7] are all running.
• [[1, 5], [5, 9]] → 1. The second starts as the first ends.

Constraints: 1 ≤ n ≤ 10⁴, 0 ≤ start < end ≤ 10⁶.

Clarifying questions

• Can a room be reused at the exact moment it is freed? Yes.
• Do I need the assignment of meetings to rooms? No, just the count.
• Is the input sorted? No.

Approach 1: count at every start

The number of rooms needed is the largest number of meetings running at the same moment. That peak is always reached at some meeting's start, because the count only goes up when a meeting starts. So check every start time.

1def min_rooms_brute(meetings: list[list[int]]) -> int:2    """At each meeting's start, count the meetings running at that moment."""3    most = 04    for start, _ in meetings:5        running = sum(1 for s, e in meetings if s <= start < e)6        most = max(most, running)7    return most

s <= start < e means the meeting has begun and not yet ended, so a meeting ending exactly at start is not counted. Time O(n²): for each of n starts, scan all n meetings. At n = 10⁴ that is 10⁸ checks — too slow.

The key insight

The reframe is the whole problem: rooms needed = most meetings running at once. Now process meetings in order of start time, as a building manager would through the day.

When a meeting starts, the manager asks one question: "Is any room free yet?" Only one room matters for that question — the one whose meeting ends soonest. If even that one is still busy, every room is busy, and a new room is needed. If it is free, reuse it.

"The room that ends soonest" among a changing set is a min-heap of end times. Its size at the end is the number of rooms ever opened.

Approach 2: a min-heap of end times

1import heapq23def min_rooms_heap(meetings: list[list[int]]) -> int:4    """Sort by start; a min-heap holds the end time of every room in use."""5    ends: list[int] = []6    for start, end in sorted(meetings, key=lambda m: m[0]):7        if ends and ends[0] <= start:            # earliest room is free again8            heapq.heapreplace(ends, end)         # reuse it9        else:10            heapq.heappush(ends, end)            # open a new room11    return len(ends)

heapreplace pops the root and pushes the new end in one sift. The heap never shrinks — every reuse is a pop followed by a push — so its final size is the number of rooms ever opened, which is the peak.

Dry run on [[2, 8], [3, 5], [6, 9], [9, 12], [4, 7]]. Sorted by start: [2, 8], [3, 5], [4, 7], [6, 9], [9, 12].

Three rooms. Correct. (The heap column is shown sorted; the real array order may differ.)

Complexity. Sorting is O(n log n), and each meeting does one heap operation of O(log n). Total O(n log n) time, O(n) space for the heap.

Approach 3: sweep two sorted arrays

Here is the surprising version. Sort all the start times, and separately sort all the end times. Which start goes with which end no longer matters — to count how many meetings are running, only the times themselves matter.

1def min_rooms_sweep(meetings: list[list[int]]) -> int:2    """Sweep sorted starts against sorted ends; count meetings in progress."""3    starts = sorted(m[0] for m in meetings)4    ends = sorted(m[1] for m in meetings)5    in_use = most = 06    e = 07    for start in starts:8        while ends[e] <= start:                  # these meetings are over9            in_use -= 110            e += 111        in_use += 112        most = max(most, in_use)13    return most

On the example, starts are [2, 3, 4, 6, 9] and ends are [5, 7, 8, 9, 12].

Same answer, 3. The while can never run past the end of ends: every meeting ends after it starts, so fewer ends than starts can be at or before any start.

Same algorithm, different bookkeeping. The heap's root is the sweep's ends[e] — the earliest end not yet used — and popping it is the sweep's e += 1. The sweep sorts every end up front; the heap discovers them one at a time. Both are O(n log n). Use the sweep (or the event version in the core lesson) when you need weights or when the peak happened. Use the heap when you need to know which meeting is in which room.

Edge cases

• One meeting: one room.
• Back-to-back meetings, [[1, 5], [5, 9]]: 5 <= 5 frees the room; one room. With < instead, the answer would be 2.
• All meetings identical, [[1, 5], [1, 5], [1, 5]]: no room is ever free; 3 rooms.
• One long meeting and many short ones: the long one holds its room the whole time; the short ones share the others.

Follow-ups

• "Which room does each meeting get?" (Meeting Rooms III). Keep a heap of (end, room id) for busy rooms and a heap of free room ids; when a meeting starts, first release every busy room with end <= start.
• "Each trip has a number of passengers; can a car with capacity C carry them all?" (Car Pooling). Use the event sweep with +passengers at pickup and -passengers at drop-off, and check the running total never exceeds C.
• "At what time is the building busiest?" Use the event sweep and record the time whenever the running count reaches a new maximum.