题目链接

LeetCode

题目描述

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2

  • -5 * 104 <= starti < endi <= 5 * 104

    解题思路

    方法一：贪心

    我们不妨想一想应该选择哪一个区间作为首个区间。
    假设在某一种最优的选择方法中，435. 无重叠区间** - 图1是首个（即最左侧的）区间，那么它的左侧没有其它区间，右侧有若干个不重叠的区间。设想一下，如果此时存在一个区间 435. 无重叠区间** - 图2，使得 435. 无重叠区间** - 图3，即区间 j 的右端点在区间 k 的左侧，那么我们将区间 k 替换为区间 j，其与剩余右侧被选择的区间仍然是不重叠的。而当我们将区间 k 替换为区间 j 后，就得到了另一种最优的选择方法。
    我们可以不断地寻找右端点在首个区间右端点左侧的新区间，将首个区间替换成该区间。那么当我们无法替换时，首个区间就是所有可以选择的区间中右端点最小的那个区间。因此我们将所有区间按照右端点从小到大进行排序，那么排完序之后的首个区间，就是我们选择的首个区间。
    如果有多个区间的右端点都同样最小怎么办？由于我们选择的是首个区间，因此在左侧不会有其它的区间，那么左端点在何处是不重要的，我们只要任意选择一个右端点最小的区间即可。
    当确定了首个区间之后，所有与首个区间不重合的区间就组成了一个规模更小的子问题。由于我们已经在初始时将所有区间按照右端点排好序了，因此对于这个子问题，我们无需再次进行排序，只要找出其中与首个区间不重合并且右端点最小的区间即可。用相同的方法，我们可以依次确定后续的所有区间。
    在实际的代码编写中，我们对按照右端点排好序的区间进行遍历，并且实时维护上一个选择区间的右端点 right。如果当前遍历到的区间 435. 无重叠区间** - 图4 与上一个区间不重合，即 435. 无重叠区间** - 图5，那么我们就可以贪心地选择这个区间，并将 right 更新为 435. 无重叠区间** - 图6。

    1. class Solution {
    2.   public int eraseOverlapIntervals(int[][] intervals) {
    3.       Arrays.sort(intervals, (a, b) -> {
    4.           return a[1] - b[1];
    5.       });
    6.       int n = 1, right = intervals[0][1];
    7.       for(int i = 1; i < intervals.length; ++i){
    8.           if(intervals[i][0] >= right){
    9.               right = intervals[i][1];
    10.               ++n;
    11.           }
    12.       }
    13.       return intervals.length - n;
    14.   }
    15. }
    1. class Solution {
    2.   public int eraseOverlapIntervals(int[][] intervals) {
    3.       // 先 end 升序，再 start 降序
    4.       // 也可以 start 不降序
    5.       Arrays.sort(intervals, (a, b) -> {
    6.           if(a[1] > b[1]){
    7.               return 1;
    8.           }else if(a[1] < b[1]){
    9.               return -1;
    10.           }
    11.           if(a[0] >= b[0]){
    12.               return -1;
    13.           }else{
    14.               return 1;
    15.           }
    16.       });
    17.       int right = intervals[0][1];
    18.       // n 为可以留下的区间个数，第一个个肯定可以留下
    19.       int n = 1;
    20.       for(int i = 1; i < intervals.length; ++i){
    21.           // 当前区间 最左侧大于等于 前面的区间最右侧 可以留下，并更新最右侧
    22.           if(intervals[i][0] >= right){
    23.               ++n;
    24.               right = intervals[i][1];
    25.           }
    26.       }
    27.       return intervals.length - n;
    28.   }
    29. }

  • 时间复杂度 O(nlog n)

  • 空间复杂度 O(1)