195. Rooms Required
An office has meetings, where meetings[i] = [start, end] means meeting i uses a room from minute start up to minute end. The room is free again at minute end, so another meeting may begin in the same room at exactly that minute.
Every meeting needs a room to itself while it runs, and a meeting cannot move rooms once it has begun. Return the smallest number of rooms that lets all meetings happen. The meetings are given in no particular order.
Example 1
- Input:
- meetings = [[2,6],[4,9],[6,8],[10,12]]
- Output:
- 2
- Explanation:
Between minutes 4 and 6 the first two meetings overlap, and between minutes 6 and 8 the second and third do. Never more than two at once, so 2 rooms are enough.
Example 2
- Input:
- meetings = [[1,2],[2,3],[3,4]]
- Output:
- 1
- Explanation:
Each meeting starts exactly as the previous one ends, so a single room is reused.
Example 3
- Input:
- meetings = [[1,5],[2,5],[3,5]]
- Output:
- 3
- Explanation:
All three are running at minute 4, so 3 rooms are needed.
Constraints
1 ≤ meetings.length ≤ 105
0 ≤ start < end ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)