Module 10 · Intervals and Sweep-Line Events

092. Minimum Meeting Rooms

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the minimum number of rooms needed for half-open meetings [start,end). Meetings can reuse a room exactly when its previous meeting ends. Ignore zero-length meetings. The input may be unsorted and is not modified.

Examples

Example 1

minimum_rooms([(0,30),(5,10),(15,20)])
=> 2

The long meeting overlaps each shorter meeting separately.

Example 2

minimum_rooms([(1,2),(2,3)])
=> 1

The same room can be reused at time two.

Example 3

minimum_rooms([])
=> 0

No meetings require no rooms.

Reveal the worked solution and reasoning

Why this mechanism works

Sort meetings by start time and keep end times of currently active meetings in a min-heap. Expire every meeting that has ended before allocating the new one. The largest active heap size is a lower bound on rooms and is achievable by reusing freed rooms.

State and boundaries

ends contains end times of meetings active at the next start. rooms is the largest simultaneous heap size observed.

Protocol

Sort meetings by start.
Skip empty meetings.
Pop all end times <= the new start.
Push the new end.
Update the maximum heap size.

Visualization

meeting starts 0,5,15
active ends: [30] -> [10,30] -> [20,30]
maximum active size=2

Python implementation

import heapq

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

minimum_rooms([(0,30),(5,10),(15,20)])

L4 minimum_rooms: ends = []
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[]

L5 minimum_rooms: rooms = 0
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[]; rooms=0

L6 minimum_rooms: for start, end in sorted(meetings):
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[]; rooms=0; start=0; end=30

L11 minimum_rooms: heapq.heappush(ends, end)
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[30]; rooms=0; start=0; end=30

L12 minimum_rooms: rooms = max(rooms, len(ends))
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[30]; rooms=1; start=0; end=30

L6 minimum_rooms: for start, end in sorted(meetings):
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[30]; rooms=1; start=5; end=10

L11 minimum_rooms: heapq.heappush(ends, end)
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[10, 30]; rooms=1; start=5; end=10

L12 minimum_rooms: rooms = max(rooms, len(ends))
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[10, 30]; rooms=2; start=5; end=10

L6 minimum_rooms: for start, end in sorted(meetings):
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[10, 30]; rooms=2; start=15; end=20

L10 minimum_rooms: heapq.heappop(ends)
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[30]; rooms=2; start=15; end=20

L11 minimum_rooms: heapq.heappush(ends, end)
meetings=[(0, 30), (5, 10), (15, 20)]; ends=[20, 30]; rooms=2; start=15; end=20

Result: 2. The long meeting overlaps each shorter meeting separately.

minimum_rooms([(1,2),(2,3)])

L4 minimum_rooms: ends = []
meetings=[(1, 2), (2, 3)]; ends=[]

L5 minimum_rooms: rooms = 0
meetings=[(1, 2), (2, 3)]; ends=[]; rooms=0

L6 minimum_rooms: for start, end in sorted(meetings):
meetings=[(1, 2), (2, 3)]; ends=[]; rooms=0; start=1; end=2

L11 minimum_rooms: heapq.heappush(ends, end)
meetings=[(1, 2), (2, 3)]; ends=[2]; rooms=0; start=1; end=2

L12 minimum_rooms: rooms = max(rooms, len(ends))
meetings=[(1, 2), (2, 3)]; ends=[2]; rooms=1; start=1; end=2

L6 minimum_rooms: for start, end in sorted(meetings):
meetings=[(1, 2), (2, 3)]; ends=[2]; rooms=1; start=2; end=3

L10 minimum_rooms: heapq.heappop(ends)
meetings=[(1, 2), (2, 3)]; ends=[]; rooms=1; start=2; end=3

L11 minimum_rooms: heapq.heappush(ends, end)
meetings=[(1, 2), (2, 3)]; ends=[3]; rooms=1; start=2; end=3

Result: 1. The same room can be reused at time two.

Why the solution is correct

Every active meeting needs a different room, giving a concurrency lower bound. A new meeting may use any room released by a popped end; if none is free, one additional room suffices. This construction meets the lower bound at the peak.

Time and space

O(n log n) time and O(n) worst-case heap/sorting space.

Common mistakes

Popping only one expired end leaves stale active meetings when several ended. Returning final heap size misses an earlier peak.

Reasoning card

State: ends contains end times of meetings active at the next start. rooms is the largest simultaneous heap size observed.

Invariant: Heap contains end times of currently active meetings.

Decision to rehearse: Sort starts; expire every meeting that ends before the next start.

Finish: Update the maximum heap size

Transfer exercise

Return actual room assignments by storing room identifiers alongside end times and recycling freed identifiers.