题目

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2

  • -5 * 10^4 <= starti < endi <= 5 * 10^4

    解题方法

    贪心

    首先对所有区间按左端从到小到大排序。
    局部最优：小区间更不会与其他区间发生重叠，故重叠区间中保留区间长度最小的，即使用最小右端判定区间重叠情况。
    全局最优：保留更多区间。
    时间复杂度O(nlogn)，空间复杂度O(1)
    C++代码：

    1. class Solution {
    2. public:
    3.   static bool cmp(const vector<int>& a, const vector<int>& b) {
    4.       return a[0]<b[0];
    5.   }
    7.   int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    8.       sort(intervals.begin(), intervals.end(), cmp);
    9.       int num = 0;
    10.       int right = INT_MAX;
    11.       for(int i=0; i<intervals.size(); i++) {
    12.           right = right < intervals[i][1] ? right : intervals[i][1];
    13.           if(intervals[i][0]>=right) {
    14.               num--;
    15.               right = intervals[i][1];
    16.           }
    17.           num++;
    18.       }
    20.       return --num;
    21.   }
    22. };