链接
题目：
思路：排序+双指针
-
先排序，对 L 正序排序，如果L相等，再按照 R 倒着排序，这样保证当L相等时，R大的在前面作为基准，R小的在后面判断是否背覆盖；
-
设第 i 个基准区间的 右端点为 x_R，第 i+1 个区间的右端点为 c_R
排完序后共三种情况：① i 覆盖 i+1：即 c_R <= x_R，则 i+1 要被删除，用count 记录；
②i 和 i+1 重叠：不需要删除，但是更新 基准 x_R 为i+1的右端点；
③i 和 i+1 隔开：不需要删除，但是更新 基准 x_R 为i+1的右端点；
注意：当 c_R = x_R 也是i+1被 i 覆盖，也要删除
Java实现：
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
Arrays.sort(intervals,new Comparator<int[]>(){
public int compare(int[]a ,int[] b){
// L 相同则按照R 倒着排
if(a[0]==b[0]){
return b[1]-a[1];
}
return a[0]-b[0];
}
});
// 不需要选最大，用for
int n=intervals.length;
int count=0; // 要被删除的
// 基准
int x_R=intervals[0][1];
for(int i=1;i<n;i++){
int c_R=intervals[i][1];
if(c_R <= x_R){ // 覆盖
count++;
continue;
}else{ //重叠 or 分隔-----更新 x_R
x_R=intervals[i][1];
}
}
return n-count;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89172.html
