问题

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

注意:
可以认为区间的终点总是大于它的起点
区间 [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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了

思路

看到这道题目时冥冥之中感觉要排序，但是究竟是按照右边界排序，还是按照左边界排序呢？
这其实是一个难点！

  • 按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的
  • 按照左边界排序，就要从右向左遍历，因为左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历
  • 如果按照左边界排序，还从左向右遍历的话，要处理各个区间右边界的各种情况

此题不需要去模拟去重复区间的行为，这是比较麻烦的，还要去删除区间
题目只是要求移除区间的个数，没有必要去真实的模拟删除区间！

本题按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了
此时问题就是要求非交叉区间的最大个数

右边界排序之后
局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉
全局最优：选取最多的非交叉区间

这里记录非交叉区间的个数还是有技巧的，如图：
leetcode-435：无重叠区间 - 图1

区间，1，2，3，4，5，6都按照右边界排好序
每次取非交叉区间的时候，都是可右边界最小的来做分割点（这样留给下一个区间的空间就越大），所以第一条分割线就是区间1结束的位置。
接下来就是找大于区间1结束位置的区间，是从区间4开始
区间4结束之后，在找到区间6，所以一共记录非交叉区间的个数是三个
总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3

  1. class Solution {
  2.     // 按照区间右边界排序
  3.     public int eraseOverlapIntervals(int[][] intervals) {
  4.         if (intervals.length == 0) 
  5.             return 0;
  7.         Arrays.sort(intervals, new Comparator<int[]>(){
  8.             public int compare(int[] interval1, int[] interval2){
  9.                 if(interval1[1] > interval2[1]){
  10.                     return 1;
  11.                 }else if(interval1[1] < interval2[1]){
  12.                     return -1;
  13.                 }else{
  14.                     return 0;
  15.                 }
  16.             }
  17.         });
  19.         int count = 1; // 记录非交叉区间的个数
  20.         int end = intervals[0][1]; // 记录区间分割点
  21.         for (int i = 1; i < intervals.length; i++) {
  22.             if (end <= intervals[i][0]) {
  23.                 end = intervals[i][1];
  24.                 count++;
  25.             }
  26.         }
  27.         return intervals.length - count;
  28.     }
  29. }
  • 时间复杂度：leetcode-435：无重叠区间 - 图2 ，有一个快排
  • 空间复杂度：leetcode-435：无重叠区间 - 图3

总结

总结如下难点：

  • 一看题就有感觉需要排序，但究竟怎么排序，按左边界排还是右边界排
  • 排完序之后如何遍历，如果没有分析好遍历顺序，那么排序就没有意义了
  • 直接求重复的区间是复杂的，转而求最大非重复区间个数
  • 求最大非重复区间个数时，需要一个分割点来做标记