LeetCode 1288：删除被覆盖的区间

╰半夏微凉° 2024-04-05 05:19 50阅读 0赞

[链接][Link 1]  
**题目**：  
![在这里插入图片描述][f9ffbbaf326e408da9bdadb75ebc8061.png]

### 思路：排序+双指针 ###

1.  先排序，对 L 正序排序，如果L相等，再按照 R 倒着排序，这样保证当L相等时，R大的在前面作为基准，R小的在后面判断是否背覆盖；
2.  设第 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/remove-covered-intervals/
[f9ffbbaf326e408da9bdadb75ebc8061.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/16b702f12a8242fba5c39b367e0fcb07.png