Medium Heap + Sort Heaps
In plain English: Figure out the maximum number of meetings happening at the same time, so you know how many rooms you need.
Sort by start time, use a min-heap of end times — if the earliest ending meeting ends before the new one starts, reuse that room; otherwise add a new room.
Prompt
Given a list of meeting time intervals [start, end], find the minimum number of conference rooms required.
Try to write it from scratch before scrolling down.
Solution
import heapq
def min_meeting_rooms(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[0]) # sort by start time
rooms = [intervals[0][1]] # heap of end times
for start, end in intervals[1:]:
if start >= rooms[0]:
heapq.heappop(rooms) # reuse room: earliest ending <= new start
heapq.heappush(rooms, end)
return len(rooms)
# Test: min_meeting_rooms([[0,30],[5,10],[15,20]]) == 2
# Test: min_meeting_rooms([[7,10],[2,4]]) == 1