Rooms Needed for Every Meeting
Problem
Given a list of meetings as (start, end) pairs, return the smallest number of rooms that lets every meeting take place. A meeting occupies its room from start up to but not including end, so a meeting that ends at 10 frees its room for one that starts at 10.
Examples
Input: meetings = [(0, 30), (5, 10), (15, 20)]
Output: 2
Why: the long meeting overlaps both short ones, but the short ones never overlap each otherInput: meetings = [(7, 10), (2, 4)]
Output: 1Input: meetings = [(1, 5), (5, 9), (9, 12)]
Output: 1
Why: edge case, back-to-back meetings share one room because the end time is exclusiveHints
0 / 3
Hand out rooms in order of start time. When a meeting starts, the only room worth checking is the one that frees up earliest.
Keep the end times of the rooms in use in a min-heap. The top of the heap is the room that becomes free first.
Sort by start. For each meeting, if the heap's smallest end is at or before this start, reuse that room by replacing its end time; otherwise push a new end time. The heap's size at the end is the answer.
Solution
Sorting by start time processes meetings in the order a building manager would see them arrive. A min-heap holds one end time per room, so its top is the room that frees up first. If that room is free by the time the new meeting starts, the meeting takes it, and heapreplace swaps the old end time for the new one in a single step; if even that room is still busy, every room is, and a new one opens. The heap never shrinks, so its final size is the peak number of rooms in use at once. The same answer comes from a sweep over sorted starts and sorted ends with two pointers. Sorting is O(n log n) and each heap step is O(log n), so time is O(n log n) and space is O(n).
import heapq
def rooms_needed(meetings):
ends = [] # end time of each room in use, earliest on top
for start, end in sorted(meetings):
if ends and ends[0] <= start: # the room freeing first is already free
heapq.heapreplace(ends, end)
else:
heapq.heappush(ends, end) # every room is busy: open another
return len(ends)
print(rooms_needed([(0, 30), (5, 10), (15, 20)])) # -> 2
print(rooms_needed([(7, 10), (2, 4)])) # -> 1
print(rooms_needed([(1, 5), (5, 9), (9, 12)])) # -> 1Stuck on the idea rather than the code? Meeting Rooms covers it.