leetcode1288. 删除被覆盖区间(java)

题目描述

难度 - 中等
leetcode1288. 删除被覆盖区间

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当 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]

贪心法

所谓区间问题，就是线段问题，让你合并所有线段、找出线段的交集等等。主要有两个技巧：
1、排序。常见的排序方法就是按照区间起点排序，或者先按照起点升序排序，若起点相同，则按照终点降序排序。当然，如果你非要按照终点排序，无非对称操作，本质都是一样的。
2、画图。就是说不要偷懒，勤动手，两个区间的相对位置到底有几种可能，不同的相对位置我们的代码应该怎么去处理。

关于本题：
对于这种区间问题，如果没啥头绪，首先排个序看看，比如我们按照区间的起点进行升序排序：
排序之后，两个相邻区间可能有如下三种相对位置：
对于这三种情况，我们应该这样处理：

对于情况一，找到了覆盖区间。

对于情况二，两个区间可以合并，成一个大区间。

对于情况三，两个区间完全不相交。

代码演示

 /*** 去除覆盖的线段* @param intervals* @return*/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 res = 0;int left = intervals[0][0];int right = intervals[0][1];for (int i = 1; i < intervals.length;i++){//情况一 找到覆盖区间if (left <= intervals[i][0] && right >= intervals[i][1]){res++;}//情况二 找到相交区间，合并if (right >= intervals[i][0] && right <= intervals[i][1]){right = intervals[i][1];}//情况三 完全不相交if (right < intervals[i][0]){left = intervals[i][0];right = intervals[i][1];}}return intervals.length - res;}