Meeting Rooms II
Meeting Rooms II is a medium Intervals problem from the Blind 75. The key pattern is sweep line, and a good solution runs in O(n log n) time.
Problem
Return the minimum number of rooms required for all half-open meeting intervals.
Examples
Example 1
Input
[[0,10],[3,7],[8,12],[11,15]]Output
2Example 2
Input
[[0,20],[4,8],[12,16]]Output
2Example 3
Input
[[8,11],[3,5]]Output
1Approach
Sort start times and end times separately and sweep both. Each start before the earliest unfinished end needs another room.
| Pattern | Sweep line |
|---|---|
| Time | O(n log n) |
| Space | O(n) |
Watch out for
Half-open intervals mean a room frees up for a meeting starting at the same moment.