The problem
Given meeting times, find the fewest rooms needed so every meeting has a room.
Input: [0,30] [5,10] [15,20] [10,14] [25,35] Output: 2
Picture it
Picture an office with rooms. Process meetings by start time. A min-heap holds the end times of meetings currently using rooms, earliest end on top. If the earliest-ending room is free by the time this meeting starts, reuse it; otherwise open a new room. The heap’s biggest size is the answer.
How to recognise it
- You need the largest number of intervals active at the same moment: rooms, servers, cars in a car park, users online.
- Each new interval can reuse a resource only if some earlier interval has finished, and the best one to check is the one that finishes earliest.
- "Repeatedly give me the earliest end, and add new ends" is what a min-heap (a priority queue that returns its smallest item in O(log n)) does well.
- A meeting that ends at 10 frees its room for a meeting that starts at 10.
- Up to 10^4 meetings on LeetCode (a premium problem), so an O(n log n) sweep is expected.
Start with brute force
The busiest moment is always the start of some meeting (the count only rises at a start). So for each meeting's start time, count how many meetings are running then, and take the largest count.
def min_rooms_brute(intervals):
best = 0
for t, _ in intervals: # the busiest moment is some start time
busy = sum(1 for s, e in intervals if s <= t < e)
best = max(best, busy)
return best
s <= t < e treats a meeting as over at its end time, matching the back-to-back rule. Time is O(n²) and space O(1). For 10^4 meetings that is 10^8 checks, which takes several seconds in Python.
From brute force to the idea
- Find the waste. For every start time, the brute force recounts all meetings, although between two consecutive starts only a few meetings begin or end.
- Sweep in start order. Sort the meetings by start. Walk through them as the day goes on.
- Track when each room frees up.
endsis a min-heap of the end times of rooms in use;ends[0]is the room that frees up first. - Reuse or open. For a meeting starting at
start: ifends[0] <= start, that room is free, so pop its old end. Then push this meeting's end, either into the reused room or into a new one. - Read off the answer. Each step pops at most one end and always pushes one, so the heap never shrinks. Its final size is the largest number of rooms ever open at once, which is the answer.
This is the key idea: sort by start, keep a min-heap of end times, reuse the room that frees first, and the heap's size is the room count.
The key idea
Sort by start + min-heap of end times. O(n log n).
Python solution
def min_meeting_rooms(intervals):
intervals.sort()
ends = [] # min-heap of when each room frees up
for start, end in intervals:
if ends and ends[0] <= start:
heappop(ends) # reuse the room that frees first
heappush(ends, end)
return len(ends)LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): for each start, all meetings are counted | O(1): a counter |
| Sort and min-heap (shown code) | O(n log n): the sort, plus one push and at most one pop per meeting | O(n): the heap can hold every meeting if all overlap |
Edge cases
- One meeting: one room.
- Back to back (
[[1, 5], [5, 10]]):5 <= 5, so the room is reused: 1. - All overlapping (
[[1, 10], [2, 10], [3, 10]]): no room ever frees, so 3. - LeetCode's example (
[[0, 30], [5, 10], [15, 20]]): 2.[15, 20]reuses the room freed by[5, 10]. - Unsorted input (
[[7, 10], [2, 4]]): sorting first gives 1. - No meetings: LeetCode guarantees at least one, but the shown code returns 0 for
[]without error. - The input is changed by
sort(), and the code needsfrom heapq import heappush, heappop.
Common mistakes
- Using
<instead of<=, so a meeting starting exactly when another ends gets a new room. - Popping all finished rooms with a
whileloop and then returninglen(ends). The heap then shrinks, so you must track the largest size separately. - Sorting by end instead of start. Meetings are then not processed in the order they begin, and the count can be wrong.
- Using a plain list and
min()instead of a heap, which makes each step O(n) and the whole O(n²).
After every meeting a room needs c minutes of cleaning before the next meeting can use it. Find the fewest rooms. For [[0, 10], [10, 20]] the answer is 1 with c = 0 and 2 with c = 5. Describe your approach, then write it if you like.
Compare with our answer
A room is busy until end + c, not end. Push that time into the heap instead; everything else stays the same.
from heapq import heappush, heappop
def min_rooms_cleaning(intervals, c):
ends = []
for start, end in sorted(intervals):
if ends and ends[0] <= start:
heappop(ends)
heappush(ends, end + c)
return len(ends)
Time O(n log n), space O(n).
A strong answer mentions: the room's free time becoming end + c, that the rest of the algorithm is unchanged, and using sorted so the caller's list is not modified.
1. A log has login and logout times for 10^5 sessions. You need the largest number of users online at the same time. Which approach fits best?
This is Meeting Rooms II: the heap holds the sessions still online, and its largest size is the peak. Merging loses how many sessions overlap, and pair counts are not the peak: [1, 3], [2, 5], [4, 7], [6, 8] has three overlapping pairs but never more than two users online.
2. Why can the shown code return len(ends) at the end, even though rooms free up during the day?
The heap size is the number of rooms ever opened: a reused room is popped and pushed back, a new room only pushes. So the final size equals the peak. If you popped every finished room, you would need a separate maximum.
3. A learner writes ends[0] < start. Which input now gives a wrong answer?
[5, 10] starts exactly when [1, 5] ends, but 5 < 5 is false, so a second room is opened and the code returns 2. In the other inputs no meeting starts exactly when the earliest-ending room frees up.
Score 60% or more and the lesson is marked complete.