删除被覆盖区间

2021-04-10  本文已影响0人  小幸运Q

将区间left小的放前面,相同left的取right更小的放后面。其实就是道排序题。

排序使用外置cmp或者static cmp不太方便,建议用lambda表达式。

bool cmp(vector<int>&a,vector<int>&b){
    if(a[0]<b[0]){
        return true;
    }
    else if(a[0]==b[0]){
        if(a[1]>b[1]){
            return true;
        }
        else{
            return false;
        }
    }
    else{
        return false;
    }
}
class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),[](vector<int>&a,vector<int>&b){return a[0]==b[0]?a[1]>b[1]:a[0]<b[0];});
        int res=1;
        int right=intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][1]<=right){

            }else{
                right=intervals[i][1];
                res++;
            }
        }
        return res;
    }
};
上一篇 下一篇

猜你喜欢

热点阅读