The problem
Given meeting times as intervals, return the fewest rooms needed to hold them all. A room freed the moment one meeting ends can host another starting at that moment.
Examples
01
- Input
intervals = [[0, 30], [5, 10], [15, 20]]
- Output
2
02
- Input
intervals = [[7, 10], [2, 4]]
- Output
1
Constraints
- 1 ≤ intervals.length ≤ 10⁴
- 0 ≤ start < end ≤ 10⁶
The idea
The rooms needed is the largest number of meetings going on at any one moment. Sweep through time: every start takes a room, every end gives one back.
Which meeting ends does not matter, only when — so sort the starts and the ends separately. Walk the starts in order; before each one, release every meeting that has ended by then (an end equal to the start counts, since the room is free). The busiest count seen is the answer.
- Time
- O(n log n)
- Space
- O(n)
Solution · every language run against every case
class Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int: # Sweep through time. Each start needs a room; each end frees one. The most rooms # busy at once is the answer. An end at the same moment as a start frees its room first. starts = sorted(s for s, _ in intervals) ends = sorted(e for _, e in intervals) busy = best = j = 0 for s in starts: while ends[j] <= s: # meetings finished by now busy -= 1 j += 1 busy += 1 best = max(best, busy) return best