微软和谷歌的几个大佬组织了一个面试刷题群,可以加管理员VX:sxxzs3998(备注CSDN),进群参与讨论和直播
1. 问题
给你一个区间列表,请你删除列表中被其他区间所覆盖的区间。
只有当 c <= a 且 b <= d 时,我们才认为区间 [a,b) 被区间 [c,d) 覆盖。
在完成所有删除操作后,请你返回列表中剩余区间的数目。
示例:
输入:intervals = [[1,4],[3,6],[2,8]]
输出:2
解释:区间 [3,6] 被区间 [2,8] 覆盖,所以它被删除了。
2. 解析
对于这种区间问题,如果没啥头绪,首先排个序看看,比如我们按照区间的起点进行升序排序:
排序之后,两个相邻区间可能有如下三种相对位置:
按照起点升序排列,起点相同时按照终点降序排列
假设得到如下排序:
对于这三种情况:
对于情况一,找到了覆盖区间,那么让覆盖区间数+1
对于情况二和情况三,如上图,在遍历到线段2时,发现线段1与线段2相交或完全不相交则更新right=2.right,left不变仍等于1.left(left和right指遍历到此轮时的参考线段范围)。left不变是因为往后遍历时后面的线段起始点不可能比left再小了,left此时没有参考价值了,所以不用更新left。
依据几种情况,我们可以写出如下代码:
class Solution { //区间问题
public int removeCoveredIntervals(int[][] intervals) {
// 按照起点升序排列,起点相同时按照终点降序排列
Arrays.sort(intervals, (a, b) -> {
if(a[0] == b[0]) return b[1]-a[1]; // 起点相同时按照终点降序排列
return a[0] - b[0]; // 按照起点升序排列
});
// 记录合并区间的起点和终点
int left = intervals[0][0];
int right = intervals[0][1];
int res = 0;
for(int i = 1; i < intervals.length; i++){
// 情况一,找到覆盖区间
if(intervals[i][0] >= left && intervals[i][1] <= right) res++;
// 情况二,情况三 更新right
if((right >= intervals[i][0] && right <= intervals[i][1]) || intervals[i][0] >= right) right = intervals[i][1];
}
return intervals.length - res;
}
}
微软和谷歌的几个大佬组织了一个面试刷题群,可以加管理员VX:sxxzs3998(备注CSDN),进群参与讨论和直播