Medium Min Heap Intervals
In plain English: Figure out the fewest meeting rooms needed so every meeting has a room, even when meetings overlap.
Sort by start time. Use a min-heap tracking room end times. For each meeting, if it starts after the earliest-ending room, reuse that room (pop and push new end). Otherwise, allocate a new room. Heap size = rooms needed.
Prompt
Given an array of meeting time intervals, 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])
rooms = [] # min-heap of end times
heapq.heappush(rooms, intervals[0][1])
for start, end in intervals[1:]:
if start >= rooms[0]: # can reuse earliest-ending room
heapq.heappop(rooms)
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