Remove Covered Intervals
Medium · intervals
Each entry of intervals is a pair [start, end] that describes a stretch of a number line, both ends included. No two entries are identical.
One interval covers another when it begins no later and finishes no earlier: interval a covers interval b if a.start <= b.start and b.end <= a.end.
Remove every interval that is covered by some other interval in the list. Return how many intervals are left.
Examples
Example 1
Input: intervals = [[1, 6], [2, 4], [3, 8]]
Output: 2
[1, 6] covers [2, 4], so [2, 4] is removed. The other two are not covered by anything.
Example 2
Input: intervals = [[1, 3], [2, 5], [4, 6]]
Output: 3
They overlap one another, but none of them lies completely inside another.
Example 3
Input: intervals = [[0, 10], [0, 5], [5, 10], [3, 7]]
Output: 1
[0, 10] covers all the others, including [0, 5] and [5, 10], which share an end with it.
Constraints
- 1 <= len(intervals) <= 10^4
- intervals[i] has exactly two numbers, start and end
- 0 <= start < end <= 10^9
- No two intervals are the same pair of numbers.