198. Swallowed Intervals
A planner lists time windows intervals[i] = [start, end], both ends included. A window [a, b] is swallowed by another window [c, d] when c <= a and b <= d, meaning it lies completely inside the other one.
Remove every window that is swallowed by some other window in the list. If two windows are exactly the same, each swallows the other, so keep just one copy of them. Return how many windows remain.
For example, [2, 4] is swallowed by [1, 6], but [3, 8] is not, because it sticks out past 6.
Example 1
- Input:
- intervals = [[1,6],[2,4],[3,8],[5,7]]
- Output:
- 2
- Explanation:
[2,4] sits inside [1,6] and [5,7] sits inside [3,8]. The windows [1,6] and [3,8] remain: 2.
Example 2
- Input:
- intervals = [[2,3],[2,3]]
- Output:
- 1
- Explanation:
The two windows are identical, so one copy is kept.
Example 3
- Input:
- intervals = [[1,2],[2,3],[3,4]]
- Output:
- 3
- Explanation:
Each window sticks out of every other one, so all 3 remain.
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)