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 <= 1000intervals[i].length == 20 <= li < ri <= 105- All the given intervals are unique.
Solutions
Solution 1: Sorting
We can sort the intervals in ascending order by their left endpoints, and if the left endpoints are the same, sort them in descending order by their right endpoints.
After sorting, we can traverse the intervals. If the right endpoint of the current interval is greater than the previous right endpoint, it means the current interval is not covered, and we increment the answer by one.
The time complexity is O(n × log n), and the space complexity is O(log n). Here, n is the number of intervals.
PythonJavaC++GoTypeScriptJavaScript
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: (x[0], -x[1]))
ans = 0
pre = -inf
for _, cur in intervals:
if cur > pre:
ans += 1
pre = cur
return ans(code-box)
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int ans = 0, pre = Integer.MIN_VALUE;
for (var e : intervals) {
int cur = e[1];
if (cur > pre) {
++ans;
pre = cur;
}
}
return ans;
}
}(code-box)
class Solution {
public:
int removeCoveredIntervals(vector<vector<int>>& intervals) {
ranges::sort(intervals, [](const vector<int>& a, const vector<int>& b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
});
int ans = 0, pre = INT_MIN;
for (const auto& e : intervals) {
int cur = e[1];
if (cur > pre) {
++ans;
pre = cur;
}
}
return ans;
}
};(code-box)
func removeCoveredIntervals(intervals [][]int) (ans int) {
sort.Slice(intervals, func(i, j int) bool {
if intervals[i][0] == intervals[j][0] {
return intervals[i][1] > intervals[j][1]
}
return intervals[i][0] < intervals[j][0]
})
pre := math.MinInt32
for _, e := range intervals {
cur := e[1]
if cur > pre {
ans++
pre = cur
}
}
return
}(code-box)
function removeCoveredIntervals(intervals: number[][]): number {
intervals.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
let ans = 0;
let pre = -Infinity;
for (const [_, cur] of intervals) {
if (cur > pre) {
++ans;
pre = cur;
}
}
return ans;
}(code-box)
/**
* @param {number[][]} intervals
* @return {number}
*/
var removeCoveredIntervals = function (intervals) {
intervals.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
let ans = 0;
let pre = -Infinity;
for (const [_, cur] of intervals) {
if (cur > pre) {
++ans;
pre = cur;
}
}
return ans;
};(code-box)
