435. 无重叠区间-蒲公英云

435. 无重叠区间

题干描述
解题思路
补充
代码实现

题干描述

力扣入口

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

解题思路

相信很多同学看到这道题目都冥冥之中感觉要排序，但是究竟是按照右边界排序，还是按照左边界排序呢？

其实都可以。主要就是为了让区间尽可能的重叠。

我来按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

此时问题就是要求非交叉区间的最大个数。

这里记录非交叉区间的个数还是有技巧的，如图：
在这里插入图片描述
区间，1，2，3，4，5，6都按照右边界排好序。

当确定区间 1 和区间2 重叠后，如何确定是否与区间3 也重贴呢？

就是取区间1 和区间2 右边界的最小值，因为这个最小值之前的部分一定是区间1 和区间2 的重合部分，如果这个最小值也触达到区间3，那么说明区间 1，2，3都是重合的。

接下来就是找大于区间1结束位置的区间，是从区间4开始。那有同学问了为什么不从区间5开始？别忘了已经是按照右边界排序的了。

区间4结束之后，再找到区间6，所以一共记录非交叉区间的个数是三个。

总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。

补充

本题其实和452.用最少数量的箭引爆气球非常像，弓箭的数量就相当于是非交叉区间的数量，只要把弓箭那道题目代码里射爆气球的判断条件加个等号（认为[0，1][1，2]不是相邻区间），然后用总区间数减去弓箭数量就是要移除的区间数量了。

代码实现

class Solution {
    // 453.无重叠区间
    public int eraseOverlapIntervals(int[][] intervals){
        Arrays.sort(intervals, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        int count = 1;
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] < intervals[i-1][1]){
                intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
                continue;
            }else{
                count++;
            }
        }
        return intervals.length - count;
    }
}
class Solution {
    // 453.无重叠区间 - 按左边排序，不管右边顺序。相交的时候取最小的右边
    public int eraseOverlapIntervals(int[][] intervals){
        Arrays.sort(intervals, (a, b) ->{
            return Integer.compare(a[0], b[0]);
        });
        int remove = 0;
        int pre = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(pre > intervals[i][0]){
                remove++;
                pre = Math.min(pre, intervals[i][1]);
            }
            else pre = intervals[i][1];
        }
        return remove;
    }
}