DSA Meeting Rooms II

The problem

Meeting Rooms II asks for the smallest number of rooms that can hold every meeting. A meeting is a start time paired with an end time. Two meetings in one room must not overlap.

Meetings that touch at one moment can share a room in this article. A meeting ending at 10 and a meeting starting at 10 never run at the same time. The answer equals the deepest overlap, which is the largest count of meetings running at one moment.

cases = [
    ([(0, 30), (5, 10), (15, 20)], 2),
    ([(9, 10), (4, 9), (4, 17), (12, 15)], 2),
    ([(0, 30), (35, 50), (60, 90)], 1),
    ([(1, 5), (2, 6), (3, 7)], 3),
]
for meetings, expected in cases:
    print("meetings", meetings, "-> rooms:", expected)

Read the last row first. All three meetings run together in the middle, so no arrangement uses fewer than three rooms. The first row peaks at two, because its two short meetings never overlap each other.

Intuition: counting what overlaps one meeting overcounts the rooms

The first idea picks one meeting and counts every meeting that overlaps it. The largest such count looks like the rooms answer. It has the right shape and the wrong meaning.

Overlapping one long meeting is not the same as running at one moment. The two short meetings below both overlap the long one. They never overlap each other, so no moment ever holds all three.

meetings = [(0, 30), (5, 10), (15, 20)]
for a in meetings:
    count = 0
    for b in meetings:
        if a[0] < b[1] and b[0] < a[1]:
            count += 1
    print("meeting", a, "overlaps", count, "meetings")

The long meeting reports three, and the true answer is two. Rooms are set by a single moment, not by one meeting's whole lifetime. The count that matters is how many meetings are in progress at the busiest moment.

Brute force: count the meetings running at every start

The brute force checks the busiest moment directly. It takes each meeting's start as a test moment. It then counts how many meetings are running at that moment.

A meeting is running at moment t when its start is not after t and its end is after t. The deepest overlap must occur at some meeting's start, so testing starts is enough. A counter records every meeting test.

def rooms_brute(meetings):
    checks = 0
    peak = 0
    for start, end in meetings:
        running = 0
        for s2, e2 in meetings:
            checks += 1
            if s2 <= start < e2:
                running += 1
        peak = max(peak, running)
    return peak, checks

peak, checks = rooms_brute([(0, 30), (5, 10), (15, 20)])
print("rooms:", peak, " meeting tests:", checks)
peak, checks = rooms_brute([(1, 5), (2, 6), (3, 7)])
print("rooms:", peak, " meeting tests:", checks)

Every start is tested against every meeting. Three meetings cost nine tests. The method is plainly correct and plainly quadratic, which makes it the right yardstick for the heap method.

The optimal solution: a heap of end times, freed in order

The heap holds the end time of every busy room, and its smallest value is the room that frees first. That one sentence is the whole method.

Meetings are visited in start order. Before a meeting is placed, every room whose earliest end is not after its start is freed. The meeting then takes a room, its end joins the heap, and the heap size is the rooms in use at that moment.

import heapq

def rooms_needed(meetings):
    ends = []
    peak = 0
    for start, end in sorted(meetings):
        while ends and ends[0] <= start:
            heapq.heappop(ends)
        heapq.heappush(ends, end)
        peak = max(peak, len(ends))
    return peak

cases = [
    ([(0, 30), (5, 10), (15, 20)], 2),
    ([(9, 10), (4, 9), (4, 17), (12, 15)], 2),
    ([(0, 30), (35, 50), (60, 90)], 1),
    ([(1, 5), (2, 6), (3, 7)], 3),
]
for meetings, expected in cases:
    result = rooms_needed(meetings)
    print("meetings", meetings, "->", result, "expected:", expected, "match:", result == expected)

All four cases pass. The peak heap size is the answer, because the heap holds exactly one end per busy room. No moment is ever tested twice.

Walkthrough: rooms for [(0, 30), (5, 10), (15, 20)]

The walk visits the meetings in start order. The state is the heap of end times after each meeting is placed. Rooms in use means the size of that heap.

import heapq

meetings = [(0, 30), (5, 10), (15, 20)]
ends = []
for start, end in sorted(meetings):
    freed = 0
    while ends and ends[0] <= start:
        heapq.heappop(ends)
        freed += 1
    heapq.heappush(ends, end)
    print("meeting", (start, end), "- freed:", freed, "- busy ends:", sorted(ends), "- rooms in use:", len(ends))

The third meeting frees the room that ended at 10 before it starts. The heap never grows past two entries. The answer is read off that peak size, and it matches the brute force count for the same day.

Complexity

The brute force tests every meeting against every start, so its time is O(n^2). The heap method sorts in O(n log n) time and does one heap push and at most one pop per meeting, so its time is O(n log n).

The brute force stores only its counters, so its extra space is O(1). The heap holds up to one end time per meeting, so its space is O(n).

for n in [3, 6, 12]:
    print("meetings", n, "- brute meeting tests:", n * n, " heap pushes:", n)

At 12 meetings the brute force pays 144 tests against 12 pushes. The heap trades a little memory for that gap. Sorting is the other price, and it is what lets rooms free in end order.

Edge cases and pitfalls

Touching meetings are the classic pitfall. A room frees when its earliest end is not after the next start, and that test must allow equality. A strict test keeps a finished room busy and invents a second room for a back-to-back day.

The empty day needs no rooms at all. A day where every meeting overlaps needs one room per meeting. Both extremes run through the same heap code below.

import heapq

def rooms_needed(meetings):
    ends = []
    peak = 0
    for start, end in sorted(meetings):
        while ends and ends[0] <= start:
            heapq.heappop(ends)
        heapq.heappush(ends, end)
        peak = max(peak, len(ends))
    return peak

def rooms_strict(meetings):
    ends = []
    peak = 0
    for start, end in sorted(meetings):
        while ends and ends[0] < start:
            heapq.heappop(ends)
        heapq.heappush(ends, end)
        peak = max(peak, len(ends))
    return peak

print("empty day:", rooms_needed([]))
print("one meeting:", rooms_needed([(9, 10)]))
print("touching pair:", rooms_needed([(0, 10), (10, 20)]))
print("touching pair, strict freeing:", rooms_strict([(0, 10), (10, 20)]))
print("back-to-back chain:", rooms_needed([(0, 5), (5, 10), (10, 15)]))
print("all at once:", rooms_needed([(1, 5), (2, 6), (3, 7)]))

The strict variant answers two rooms for a pair that truly needs one. That single character, equality in the freeing test, is the whole difference. The correct rows need no special handling.