无重叠区间（贪心算法）-蒲公英云

无重叠区间（贪心算法）

た入场券 2022-12-28 14:23 287阅读 0赞

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

注意:

可以认为区间的终点总是大于它的起点。
区间 [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）
链接：https://leetcode-cn.com/problems/non-overlapping-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    struct cmp{
        bool operator()(vector<int>&a1,vector<int>&a2){
            return a1[0]<a2[0];
        }
    };
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
       sort(intervals.begin(),intervals.end(),cmp());
       int i=0;
       int num=0;
       for(int j=1;j<intervals.size();j++){
           if(intervals[j][0]>=intervals[i][1]){
               i=j;
           }
           else{
               num++;
               if(intervals[j][1]<intervals[i][1]){
                   i=j;
               }
           }
       } 
       return num;
    }
};