You are given intervals, the meetings of one day, each [start, end] with start < end. A
room holds one meeting at a time. A meeting that ends at time t frees its room for a meeting
that starts at t.
Return the smallest number of rooms that can hold every meeting.
Example 1
- Input
- intervals = [[9, 12], [10, 11], [11, 14], [13, 15]]
- Output
- 2
[9, 12] and [10, 11] overlap, so two rooms. [11, 14] takes the room freed at 11, and [13, 15] the one freed at 12.Example 2
- Input
- intervals = [[1, 5], [2, 6], [3, 7]]
- Output
- 3
Constraints
intervalsholds 1 to 10⁴ meetings.- 0 ≤
start<end≤ 10⁶
Show the pattern
Intervals, Heap
Taking meetings in order of start time, you need to know when the earliest-finishing room frees up. A min-heap of end times gives that at once, and its size is the number of rooms in use.
See intervals in a visualiserShow the approach
Sort the meetings by start time, and keep a min-heap of the end times of the rooms in use. For each meeting, if the earliest end time in the heap is at most this meeting's start, that room is free again: pop it. Then push this meeting's end time (it takes that room, or a new one). The heap only grows when every room is busy, so its final size is the number of rooms needed.
Another way: sort the start times and the end times separately and sweep through them together, adding one for each start and taking one away for each end at or before it; the highest count is the answer.
Time: O(n log n) · Space: O(n)