Meeting Rooms II
The peak number of simultaneous meetings is the number of rooms needed.
Heap of End Times
Problem
Given a collection of meeting time intervals, determine the smallest number of rooms required to schedule every meeting without overlap in the same room. Meetings that end exactly when another begins do not conflict, so one room can be reused at that boundary.
Examples
Input: [[0,30],[5,10],[15,20],[18,25],[25,35]]
Output: 3
Input: [[0,10],[10,15],[20,25]]
Output: 1
The Goal
Find the fewest rooms that fit every meeting, with no two overlapping meetings in one room. A meeting that ends exactly when another starts frees its room in time.
That's the most meetings in progress at any one moment. For [[0,30],[5,10],[15,20],[18,25],[25,35]], three are in progress at time 18, so you need 3 rooms.
Rooms are peak overlap
The fewest rooms is the most meetings in progress at the same time.
Track the meetings in progress. The most at once is the answer.
Key Idea: A Heap of End Times
Take meetings in order of start time. Keep the end times of the meetings in progress on a min-heap, so the earliest end sits at the root.
When a meeting starts, pop every end at or before its start: those rooms are free. Then push its end. The heap's size is the number of rooms in use, and the biggest size it reaches is the answer.
The earliest end is the first room that can free up.
In [20, 30, 25], check 20 first.
The Algorithm
import heapq
def min_meeting_rooms(intervals):
# The end times of the meetings in progress, earliest at the root.
heap = []
rooms = 0
intervals = sorted(intervals, key=lambda m: m[0])
for start, end in intervals:
while heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
rooms = max(rooms, len(heap))
return roomsSorting with key=lambda m: m[0] orders by start and keeps the given order on a tie.
The pop is a while, not an if: several meetings can end before the next one starts. The answer is the biggest size the heap reached, not its size at the end.
| Approach | Time | What it tracks |
|---|---|---|
| Sort, then a min-heap | O(n log n) | The earliest end among meetings in progress |
| Compare every pair | O(n^2) | Every overlap |
| Sweep sorted starts and ends | O(n log n) | Starts and ends as events |
Walkthrough
Run it on the five meetings above, sorted by start.
[0,30] and [5,10] overlap: the heap is [10, 30]. At 15, 10 has ended, so it pops and 20 goes in. At 18 the earliest end, 20, is still ahead, so 25 joins: [20, 30, 25], three in progress.
At 25, both 20 and 25 pop. The heap ends as [30, 35], and rooms stays 3.
Checkpoint · predict the next step
Step 10 of 27 on the stage: The earliest end in the heap is 10, at or before 15: that meeting is over, and its room is free.
heap = [10, 30] · in progress 2 · rooms 2
Pitfalls
- Pop when
heap[0] <= start. With<, back-to-back meetings[0,10],[10,20],[20,30]take 2 rooms instead of 1. - Pop in a loop. Several rooms can free up before one start.
- Sort first. Try Break it with meetings given out of order.
- Return the biggest heap size, not the last one.
For meetings [0,10] and [10,15], how many rooms do you need?
Complexity
Sorting costs O(n log n). Each meeting is pushed once and popped at most once, and each heap operation costs O(log n), so the loop is O(n log n) too.
The heap can hold every meeting at once, so space is O(n). A sweep over sorted starts and sorted ends has the same bounds.
Sorting and heap tracking
- Sort by startTime order.dominantO(n log n)
- Pop ended meetingsAt most once each.dominantO(n log n)
- Push each endOnce each.dominantO(n log n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n log n) | 33 | 664 | 10K | 132.9K |
| O(n) | 10 | 100 | 1K | 10K |
A sort, then a heap of end times.
In short
Sort meetings by start, and keep a min-heap of end times of ongoing meetings. For each meeting, pop any that have ended before it starts, then push its end; the heap's max size over the run is the room count. A sorted-starts/sorted-ends two-pointer sweep also works.
Common mistake
Comparing each meeting to all others (O(n²)) rather than tracking active meetings with a heap.