Problem 38 · Intervals

Meeting Rooms II

MediumClassic DSA & systems

01Problem

Given meeting time intervals [start, end), return the minimum number of rooms required.

02Key insight

Sort by start and keep a min-heap of end times for rooms in use; reuse the room whose meeting ends earliest if it ends by the new start. Heap size peak = answer.

03Solution

solution.pypython10 lines

import heapq

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    ends: list[int] = []
    for start, end in sorted(intervals):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)

Try it first.

TimeO(n log n)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert min_meeting_rooms([[0, 30], [5, 10], [15, 20]]) == 2
assert min_meeting_rooms([[7, 10], [2, 4]]) == 1
assert min_meeting_rooms([[1, 5], [5, 10]]) == 1
assert min_meeting_rooms([]) == 0

04Staff-level follow-up

Also need which room each meeting gets, with rooms of different capacities? Keep a heap of free room ids plus a heap of (end, room) busy rooms; capacity constraints turn it into interval scheduling with matching.