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.
int removeCoveredIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
}
);
int count = 0;
vector<int> prev;
for (auto& interval : intervals) {
if (prev.empty() || interval[0] > prev[0] && interval[1] > prev[1]) {
count++;
prev = interval;
}
}
return count;
}Follow-up:
What if the intervals are not disjoint?
