leetcode435. 无重叠区间

一:论语

道不同 不相为谋 我们没有理由拿着自己的评判标准 去看待别人所经历的事情,重来就没有真正的感同身受,我们能做的就是尊重他人的看法 ,保留自己的态度。

二:题目

三:上码

class Solution {
          
   
public:
    /**
        思路:1.我们这里还是按照区间数组的第二个元素进行升序处理
               [[1,2],[1,3],[2,3],[3,4]]
               这里只要我们我们的区间数组的右边界小于下一个数组的左边界的话 那么我们最终的区间就是
               互不重叠的。
    */    
    static bool cmp(const vector<int> & v1,const vector<int>& v2) {
          
   
        return v1[1] < v2[1];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
          
   

        sort(intervals.begin(),intervals.end(),cmp);

        int temp = intervals[0][1];//第一右边界
        int count = 1;//满足要求的区间数组数(记录第一 个区间数组)
    
        for(int i = 0; i < intervals.size(); i++) {
          
   
            if(temp <= intervals[i][0]){
          
   //如果小于左边界的话,那就更新右边界,同时记录满足要求的区间数组数
                temp = intervals[i][1];
                count++;
            }
        }

        return intervals.size() - count;

    }
};

加油 晚安 陌生人

经验分享 程序员 微信小程序 职场和发展