class Solution {
public:
int removeCoveredIntervals(vector<vector<int>>& intervals) {
}
};
1288. 删除被覆盖区间
给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。
在完成所有删除操作后，请你返回列表中剩余区间的数目。
示例：
输入：intervals = [[1,4],[3,6],[2,8]] 输出：2 解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。
提示：
1 <= intervals.length <= 10000 <= intervals[i][0] < intervals[i][1] <= 10^5i != j：intervals[i] != intervals[j]原站题解
java 解法, 执行用时: 5 ms, 内存消耗: 41.6 MB, 提交时间: 2022-12-09 16:22:10
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, range = 0;
for (int i = 0; i < intervals.length; i++) {
int[] ints = intervals[i];
int b = ints[1];
if (b > range) {
ans += 1;
range = b;
}
}
return ans;
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 15.2 MB, 提交时间: 2022-12-09 16:21:10
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
n = len(intervals)
intervals.sort(key=lambda u: (u[0], -u[1])) # 左端点递增，右端点递减
ans, rmax = n, intervals[0][1]
for i in range(1, n):
if intervals[i][1] <= rmax:
ans -= 1
else:
rmax = max(rmax, intervals[i][1])
return ans
python3 解法, 执行用时: 84 ms, 内存消耗: 15.3 MB, 提交时间: 2022-12-09 16:20:02
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
n = len(intervals)
ans = n
for i in range(n):
for j in range(n):
if i != j and intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:
ans -= 1
break
return ans