Description
Find the minimum number of rooms for meetings with start < end. A room is reusable at its meeting's end time.
Solution
from heapq import heappush, heappop
def min_meeting_rooms(intervals):
active = []
best = 0
for start,end in sorted(intervals):
while active and active[0] <= start:
heappop(active)
heappush(active,end)
best = max(best,len(active))
return bestExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[[1,4],[2,5],[5,6]]]- Output
2
Two meetings overlap; a room is free for the last.
Example 2
- Input
[[[1,2],[2,3]]]- Output
1
The same room can be reused at time 2.
Example 3
- Input
[[]]- Output
0
No meetings require zero rooms.
Approach
Process meetings by start time and remove all finished meetings from an end-time min-heap.
Time & space
O(n log n) time; O(n) space. Here n is the input length.