1288. Remove Covered Intervals¶
Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.
The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.
Return the number of remaining intervals.
Example 1:
Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.
Example 2:
Input: intervals = [[1,4],[2,3]]
Output: 1
Constraints:
1 <= intervals.length <= 1000intervals[i].length == 20 <= li <= ri <= 105- All the given intervals are unique.
Analysis¶
Intervals problems can usually be solved by using a sorting algorithm (or an inherently greedy algorithm). For this problem, we can sort the interval by the start time. For two intervals a and b, where a[0] <= b[0], we can know that if a[1] >= b[1], the b interval will be covered by a. We can also know that c will also be covered if a[1] > c[1]. We don't need to know anything about the start time to check if the current interval can be covered, because the start time is always less than the current end time, and are sure that the current interval's start time is less than the end time.
To find out the number of uncovered intervals, we just need to know the previous starting time (since it will always be greater than all the intervals' starting time in front of it), and the current maximum ending time (we need to keep track of it because the end time is unsorted). If the current start time is greater than the previous start time and the global end time, then we count the current interval as a newly uncovered interval.
- Time: O(n \times \log(n))
- Space: O(1)
Code¶
class Solution {
public:
int removeCoveredIntervals(vector<vector<int>>& a) {
sort(a.begin(), a.end());
int res = 0, left = -1, right = -1;
for (auto i : a) {
// count the number of uncovered intervals
if (left < i[0] && right < i[1]) {
res ++;
left = i[0];
}
right = max(right, i[1]);
}
return res;
}
};