说在前面
🎈今天给大家带来的是算法练习,题目为"删除被覆盖区间"。
题目描述
给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。\
只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。\
在完成所有删除操作后，请你返回列表中剩余区间的数目。\
示例：
输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。提示：
1 <= intervals.length <= 1000
0 <= intervals[i][0] < intervals[i][1] <= 10^5
对于所有的 i != j：intervals[i] != intervals[j]思路分析
题目描述很清晰，就是要我们把给出列表中的小区间删除，最后返回剩余元素的个数。这里的小区间是指列表中有包含该区间的大区间时，该区间即为小区间，即题目所说的只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖,如图：
相对于区间[1,4]来说,[2,4]是小区间，但相对于[1,5]来说，[1,4]又是小区间，所以[[1,4],[2,4],[1,5]]删除掉小区间后应该只剩下[[1,5]],具体解题思路如下：
- 列表排序
我们要让做端点小的排在前面，如果左端点相等则让右端点大的排在前面，只要我们只需要一次遍历比较右端点即可得到答案。
intervals = intervals.sort((a,b)=>{
if(a[0] == b[0]) return b[1] - a[1];
return a[0] - b[0];
})- 遍历列表比较右端点
let r = intervals[0][1];
for(let i = 1; i < intervals.length; i++){
if(r >= intervals[i][1]) res--;
else r = intervals[i][1];
}AC代码
/**
* @param {number[][]} intervals
* @return {number}
*/
var removeCoveredIntervals = function(intervals) {
let res = intervals.length;
intervals = intervals.sort((a,b)=>{
if(a[0] == b[0]) return b[1] - a[1];
return a[0] - b[0];
})
let r = intervals[0][1];
for(let i = 1; i < intervals.length; i++){
if(r >= intervals[i][1]) res--;
else r = intervals[i][1];
}
return res;
};说在后面
🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
