个人技术分享

原题:链接

代码:
 

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),[](const vector<int>& a,const vector<int>& b){
            if(a[0]!=b[0])return a[0]<b[0];
            return a[1]>b[1];
        });
        int res = intervals.size(),r = 0;
        for(auto &q :intervals){
            if(q[1]<=r){
                res--;
            }
            else{
                r = max(r,q[1]);
            }
        }
        return res;

    }
};

题解:

        给出的数据是vector<int> vec  = {1 , 2};表示一个以1为左端点,2为右端点的区间;


         对于人来讲,比较一个区间是否可以被另一个区间覆盖是很容易的,我们通过左右区间来判断即可,转换到计算机中,如何让电脑判断是否可以被覆盖?就是利用左右区间的值:如果A区间左端点比B区间更左,右端点比B更右,那么A将覆盖B;

        即:我们应该尽量先找到类似A这种区间,然后看到B时,比较它们的左右端点够不够“左”,够不够“右”,从而将B覆盖掉;

        那么A区间具有的特征:很“左”:即它的vector的0号元素比B区间的号元素更小;也就是说,0号元素更小的区间应该排在前边,同样地,右端点如果更大,即:vector中的1号元素比B区间的1号元素更大,则应该排在前边,左端点相同时,右端点大则排序在前,因为它更有可能把后边的右端点不太大的区间给覆盖掉。

        以上这段话,对应我们写的sort函数那一段代码,怎么排序,我们对应的代码是Lambda表达式那一段代码;

        排序后,我们初始值设为vector<vector<int>>的size,找到一个减去一个,最终return即可;

        r则是遍历时维护的右端点的最大值,我们知道我们做完排序工作后,右端点大者覆盖能力更强,所以在范围for中,我们写了谁的右端点<=r,则被覆盖(res--);反之,更新我们的右端点最大值 r;