力扣435-无重叠区间

一、原题题目

1.1 题目

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

注意:

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

1.2 示例

示例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
解释： 你不需要移除任何区间，因为它们已经是无重叠的了。

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

二、解题思路

2.1 利用【贪心+右边界排序】解题

解题思路

看了这个题想了很久，总觉得是之前做过，但是就是没想到具体的方法，之后在题解中才回忆到这是一道区间调度问题，例如今天有很多事情安排要做，每件事情有起始时间点和结束时间点，怎么选择安排时间做事才能使处理的事情数最多。

这里我们对每个区间的右边界进行从小到大排序，然后依次选择结束时间早并且没有区间重合的区间，有重合的就是我们需要剔除的区间。至于这样下来，为什么就是剔除的最少的？我们可以这么理解，剔除的最少也就是我们要保留的最多，为了使后面能选择的更多我们需要后面留下的空间更大，所以我们每次挑区间右边界最小的区间更合理，这里就是贪心的思路了，每次选右边界最小的就是局部最优，让后面的空间更大。这样处理完得到的结果就是全局最优。这里借用题解里一位大佬的动图演示过程。

详细代码（Java）

public int eraseOverlapIntervals(int[][] intervals) {
    if(intervals.length == 0)   return 0;       // 如果数组没有元素，返回0
    Arrays.sort(intervals,(a,b)->a[1]-b[1]);		// 对数组元素按第二个值(右边界)进行升序排序
    int count = 0;                              // 统计重叠区间的个数,初始化为0
    int x_end = intervals[0][1];                // 记录现在的结束边界
    for (int i = 1;i<intervals.length;i++) {    // 从第二个元素开始遍历每一个元素
        if (intervals[i][0]<x_end){             // 当前元素的左边界小于记录的结束边界则表示重合
            count++;                            // 统计重合区间个数+1
        }
        else x_end = intervals[i][1];           // 当前元素的左边界不小于记录的右边界则表示不重合，更新记录的结束边界
    }
    return count;
}

代码执行结果

2.2 利用【贪心+左边界排序】解题

解题思路

在题解里还看到这样的一个思路，是对每个元素的第一个值（左边界）进行排序，碰到有重叠的区间我们选择第二个值（右边界）更小的区间保留，这里其实跟上面的思路一样，为了让后面的空间更大更能选出更多的区间，达到全局最优。代码也比较容易但性能比上一个好，这里不太明白为什么？

详细代码（Java）

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0)  return 0;           // 如果数组没有元素，返回0
    Arrays.sort(intervals,(a,b)-> a[0]-b[0]);       // 对数组元素按第一个值(左边界)进行升序排序
    int count = 0;                                  // 统计重叠区间的个数,初始化为0
    int end = intervals[0][1];                      // 记录现在的结束边界
    for (int i = 1;i<intervals.length;i++){         // 从第二个元素开始遍历每一个元素
        if (intervals[i][0]<end){                   // 当前元素左边界小于记录的结束边界则表示有重合
            count++;                                // 统计重合区间个数+1
            end = Math.min(end,intervals[i][1]);    // 更新记录的结束边界为重叠区间中右边界更小的值
        }
        else end = intervals[i][1];                 // 当前元素左边界不小于记录的右边界则表示没有重合，更新结束边界
    }
    return count;
}