Description
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 <= 1000
intervals[i].length == 2
0 <= li <= ri <= 105
- All the given intervals are unique.
Solutions
Solution 1
Intuition
- ascending sort by the start of interval, if start are equal then descending sort by the end of interval;
- store the biggest end point, and update it
- if end point smaller than the biggest end point, this interval is covered.
Code
class Solution {
public:
static bool compare(vector<int>& a, vector<int>& b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
}
int removeCoveredIntervals(vector<vector<int>>& intervals) {
if (intervals.size() == 1) {
return 1;
}
sort(intervals.begin(), intervals.end(), compare);
int end = intervals[0][1];
int count = intervals.size();
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][1] <= end) {
count--;
} else {
end = intervals[i][1];
}
}
return count;
}
};
Complexity
- Time: O(nLogn)
- Space: O(1)
Top comments (0)