Remove Covered Intervals
Given a list of intervals, remove the covered intervals and return the number of remaining intervals. An interval is covered by another interval if its start and end points are both within the other interval.
Constraints:
- 1 <= intervals.length <= 1000
- intervals[i].length == 2
- 0 <= intervals[i][0] < intervals[i][1] <= 10^5
Examples:
Input: [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Intervals [3,6] and [1,4] are covered by [2,8], so we remove them and return 2.
Solutions
Sorting
Time: O(n log n)Space: O(n)
We sort the intervals based on their start points and end points. If two intervals have the same start point, we sort them based on their end points in descending order. Then we iterate through the sorted intervals and count the number of intervals that are not covered by any other interval.
def removeCoveredIntervals(intervals):
intervals.sort(key=lambda x:
(x[0], -x[1]))
count = 0
prev = None
for interval in intervals:
if prev is None or interval[0] > prev[0] and interval[1] > prev[1]:
count += 1
prev = interval
return countFollow-up:
What if the intervals are not disjoint?
