LeetCode/1288. 删除被覆盖区间

1288. 删除被覆盖区间

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

只有当 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]

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

遇到区间问题，先排序。对于本题，按照第一个元素升序，第二个元素降序排列，这样排列过后就会出现三种情况：1. 前一个区间完全覆盖当前区间，那么就可以将当前区间删除；2. 两个区间相交，这时候取两个区间的并集，合并成一个大区间；3. 两个区间没有交集，这时候由于数组已经排过序，所以直接将临时比较的区间[left, right]赋值成当前区间即可。

具体代码如下：

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 result = 0;
        for (int i = 1; i < intervals.length; i++) {
            int[] temp = intervals[i];

            //第一种情况，[left, right]完全覆盖当前区间
            if (left <= temp[0] && right >= temp[1]) {
                //记录被覆盖区间个数
                result++;
            }
            //第二种情况，[left, right]与temp区间交叉
            if (right >= temp[0] && right <= temp[1])
                right = temp[1];
            //第三种情况，两个区间没有任何交叉
            if (temp[0] >= right) {
                left = temp[0];
                right = temp[1];
            }
        }
        //由于记录的是被覆盖数组个数，题目要求剩余个数
        return intervals.length - result;
    }
}