[数据结构与算法]【贪心算法】435. 无重叠区间

【贪心算法】435. 无重叠区间

题目

解析

题目要求最少需要移除区间的个数 一般都是贪心算法,也就是 要让互不重叠的区间个数最多 那么重叠的区间个数最少！

保留不重叠的区间，如果选择的区间结尾越小，那么这个区间和其他区间相互重叠的可能性越小，不重叠个数越多.

首先按照区间结尾递增的顺序进行排序，然后标记第一个区间的结尾为prev，从第二个区间开始遍历，让后面的每一个区间的开始与该结尾进行比较，如果比他小，说明发生了重叠，removed++,如果不重叠，那么标记第二个区间的结尾为prev, 然后接着向下开始遍历。

像这个案例：[1,2]与[1,3]重叠，那么prev 指向[2,4]（[1,2]与[2,4] 不重叠） , 但是[2,4]与[1,5] 发生重叠 最后只保留两个。

那么，可能要问，尽管prev已经变化了，但是如果前面的区间和后面的区间发生了重叠怎么办？是不是更新了prev就不需要考虑前面的区间和后面的区间的重叠，比如这里的[1,2]与[1,5], 但是prev已经指向了[2,4]

答案是：不需要考虑，一旦prev往后移动了，只需要考虑后面的元素与prev有没有重叠，因为prev([2,4])与前面某一个区间([1,2]) 不重叠，那么说明prev的开始大于或者等于前面这个区间的结尾，所以前面这个区间一旦与prev后面的某一个区间发生了重叠（前面该区间的结尾大于或者等于prev后面某一个区间开始），那么prev的结尾一定大于后面该区间的开始，这样又发生了一次重叠，所以不用考虑。

intervals = [[1,2],[1,3],[2,4],[1,5]]

代码

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        //  数组长度最小为1  不需要判空

        //  题目要求最少需要移除区间的个数  一般都是贪心算法
        // 也就是 要让互不重叠的区间个数最多  那么重叠的区间个数最少！
        
        // 保留不重叠的区间，如果选择的区间结尾越小，那么这个区间和其他区间相互重叠的可能性越小，不重叠个数越多
        
        int n = intervals.size();

        // 按照区间的结尾从小到大的顺序排序
        sort(intervals.begin(),intervals.end(),[](vector<int> &a,vector<int> &b){return a[1] < b[1];});

        int removed = 0,prev = intervals[0][1];// 取出 第一个区间的结尾

        for(int i = 1; i < n; i++)
        {
            // 取出后面一个区间的开始  如果比第一个区间的结尾小  说明 重叠
          if(intervals[i][0] < prev)
          {
              removed++;
          }  
          else{
              prev = intervals[i][1];// 如果不重叠 更新prev
          }
        }
        return removed;

    }
};