LeetCode_区间问题_中等_1288.删除被覆盖区间

淡淡的烟草味﹌ 2023-10-06 22:24 29阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

**只有当 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\] <= 105  
对于所有的 i != j: intervals\[i\] != intervals\[j\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/remove-covered-intervals

## 2.思路 ##

（1）排序  
思路参考[一文秒杀所有区间相关问题][Link 1]。

## 3.代码实现（Java） ##

//思路1————排序
    public int removeCoveredIntervals(int[][] intervals) {
        
        //res保存被覆盖的区间数，初始值为0
        int res = 0;
        //按照区间的左端点对所有区间进行升序排序
        Arrays.sort(intervals, (a, b)-> {
        
            if (a[0] == b[0]) {
        
                return b[1] - a[1];
            } else {
        
                //如果Comparator接收的返回值为正数，就会交换 a 和 b
                return a[0] - b[0];
            }
        });
        //记录合并区间的左端点和右端点
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
        
            int[] curInter = intervals[i];
            //找到被覆盖的区间
            if (left <= curInter[0] && curInter[1] <= right) {
        
                res++;
            }
            //找到相交区间，更新右端点
            if (left <= curInter[0] && right <= curInter[1]) {
        
                right = curInter[1];
            }
            //找到的区间无交集，更新左右端点
            if (right <= curInter[0]) {
        
                left = curInter[0];
                right = curInter[1];
            }
        }
        return intervals.length - res;
    }

[Link 1]: https://mp.weixin.qq.com/s/Eb6ewVajH56cUlY9LetRJw