Meeting Rooms II: Minimum Rooms With a Min-Heap or a Sweep

Meeting rooms comes in two sizes. The small question asks whether one person can attend every meeting. The bigger one, usually called Meeting Rooms II, asks how many rooms a set of meetings needs. Both answers come from sorting, and the second has two standard solutions, a min-heap and a two-list sweep, that turn out to count exactly the same thing.

The problem it solves

Each meeting is a pair (start, end), and a meeting occupies its room from start up to, but not including, end. So a meeting that ends at 10 and one that starts at 10 can share a room.

• Meeting Rooms I: can one person attend all of them, with no two overlapping?
• Meeting Rooms II: what is the minimum number of rooms so that every meeting has one?

For [(0, 30), (5, 10), (15, 20)] the answers are "no" and 2: the long meeting needs its own room, and the two short ones can share the other.

The intuition

For the first question, sort by start time. If any meeting starts before the previous one ends, there is a clash; otherwise there is not. Only neighbours in sorted order need checking, because a clash with anything earlier would also be a clash with the neighbour.

For the second question, the key fact is that the number of rooms needed equals the largest number of meetings running at the same instant. You need at least that many, since those meetings all overlap. And that many is enough: handle meetings in start order, give each one any room that is free, and a new room is opened only when every room is busy, which means the number of live meetings has just reached a new high.

That leaves two ways to track "how many are live right now":

• A min-heap of end times. The heap holds one end time per room in use. For each meeting in start order, look at the smallest end time. If that meeting has finished, reuse its room, replacing its end time; otherwise open a new room. The heap's final size is the room count.
• Two sorted lists. Pull all the starts into one sorted list and all the ends into another, and sweep. A start claims a room; every end at or before that start frees one. The highest the counter reaches is the answer. It works because only the count matters, never which meeting sits in which room.

Watch it run

The animation sweeps the lesson's three meetings, 0–30, 5–10 and 15–20. It sorts the starts and the ends into separate lists, dropping the pairing on purpose, then walks the clock. At t = 5 nothing has ended yet, so a second room is claimed. By t = 15 the meeting that ended at 10 has freed its room, and the third meeting slides into it: the counter never passes 2.

The code

Meeting Rooms I. Sorting tuples sorts by start first:

def can_attend_all(meetings):
    meetings = sorted(meetings)
    return all(meetings[i][1] <= meetings[i + 1][0]      # ends before next starts
               for i in range(len(meetings) - 1))

print(can_attend_all([(0, 30), (5, 10), (15, 20)]))   # False
print(can_attend_all([(7, 10), (2, 4)]))              # True

Meeting Rooms II, both ways. heapq.heapreplace pops the smallest end time and pushes the new one in a single step, which is exactly "reuse the room that frees up first":

import heapq

def min_rooms_heap(meetings):
    ends = []                                  # end times of rooms in use
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:          # earliest-ending room is free
            heapq.heapreplace(ends, end)       # reuse it
        else:
            heapq.heappush(ends, end)          # open a new room
    return len(ends)

def min_rooms_sweep(meetings):
    starts = sorted(s for s, _ in meetings)
    ends = sorted(e for _, e in meetings)
    rooms = peak = j = 0
    for s in starts:
        while ends[j] <= s:                    # a meeting ended by now
            rooms -= 1
            j += 1
        rooms += 1
        peak = max(peak, rooms)
    return peak

schedule = [(0, 30), (5, 10), (15, 20)]
print(min_rooms_heap(schedule), min_rooms_sweep(schedule))   # 2 2
print(min_rooms_heap([(1, 5), (5, 9)]))                      # 1
print(min_rooms_heap([]), min_rooms_sweep([]))               # 0 0

Both against a brute force that counts, at every start time, how many meetings are live, on 3,000 random schedules. For intervals that include their start and exclude their end, the busiest instant is always some meeting's start, so checking only those points is enough:

import random

def brute_force(meetings):
    # rooms needed = most meetings live at one instant; with [start, end)
    # intervals that maximum is reached at some start time
    return max((sum(s <= t < e for s, e in meetings) for t, _ in meetings),
               default=0)

random.seed(9)
ok = True
for _ in range(3000):
    meetings = []
    for _ in range(random.randint(0, 9)):
        s = random.randint(0, 20)
        meetings.append((s, s + random.randint(1, 8)))
    want = brute_force(meetings)
    ok &= min_rooms_heap(meetings) == want == min_rooms_sweep(meetings)
    ok &= can_attend_all(meetings) == (want <= 1)
print(ok)                                                    # True

The complexity

Sorting dominates both versions. With n meetings:

• Heap: O(n log n) to sort, plus one heap operation of O(log n) per meeting. O(n log n) time, O(n) space for the heap in the worst case, when every meeting overlaps every other.
• Sweep: two sorts, O(n log n), then a single linear pass, because j only moves forward. O(n) space for the two lists.
• Meeting Rooms I: one sort and one pass, O(n log n) time.

In an interview, the heap version is the easier one to extend: if the follow-up asks which room each meeting gets, store (end, room_id) pairs in the heap and the assignment falls out.

Where it goes wrong

• Getting the tie wrong. Whether a meeting ending at 10 frees its room for one starting at 10 is a spec question. The code above says yes, with <=. If the problem treats both endpoints as occupied, the comparison becomes < and the answer for [(1, 5), (5, 9)] becomes 2. Ask before coding.
• Sorting by end time. Room assignment must process meetings in start order. Sorting by end time is the rule for a different problem, choosing the most non-overlapping meetings, and gives wrong room counts here.
• Counting overlaps pairwise. "Number of pairs that overlap" is not the room count. The chain (0, 2), (1, 4), (3, 6), (5, 8) has three overlapping pairs but never more than two meetings live at once, so it needs 2 rooms.
• Checking only the last room used. The free room is the one that ends earliest, not the one assigned most recently. For (0, 3), (1, 10), (4, 6), checking the last room sees it busy until 10 and opens a third room, while the first room has been free since 3. That is why the structure is a min-heap.

How to say it in an interview

"The number of rooms is the maximum number of meetings live at once. I sort by start time and keep a min-heap of end times, one per room in use. For each meeting, if the earliest end time is at or before its start, that room is free and I replace its end time; otherwise I push a new one. The heap size at the end is the answer: O(n log n) time, O(n) space. Equivalently, I can sort starts and ends separately and sweep with a counter, since only the count matters. First I'd confirm whether a meeting ending at 10 frees the room for one starting at 10."

The sort-by-start sweep is the same first move as merge intervals, and the "keep only the smallest end time handy" heap is introduced in the priority queue lesson.