196. Fewest Cancellations
A hall receives intervals of booking requests, where each [start, end] asks for the hall from time start until time end. The hall is free again at end, so one booking may begin exactly when another finishes.
Some requests overlap, so a few must be cancelled. Return the smallest number of requests to cancel so that no two of the remaining ones overlap. Identical requests overlap each other, so only one of them can stay.
Example 1
- Input:
- intervals = [[1,4],[2,5],[5,8],[3,6]]
- Output:
- 2
- Explanation:
Keeping [1,4] and [5,8] leaves a gap-free pair; the other two overlap something kept, so 2 requests are cancelled.
Example 2
- Input:
- intervals = [[1,3],[3,5],[5,7]]
- Output:
- 0
- Explanation:
Each request starts exactly when the previous one ends, so none overlap and nothing is cancelled.
Example 3
- Input:
- intervals = [[2,9],[2,9],[2,9]]
- Output:
- 2
- Explanation:
Identical requests overlap each other, so only one survives and 2 are cancelled.
Constraints
1 ≤ intervals.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(1)