LeetCode-757. 设置交集大小至少为2，贪心算法的使用

题目分析

① .排序

为了取的元素个数最少，要使取的元素值能被更多的区间覆盖，把区间结束值小的排前面，这样在该区间中取的元素可能在下个区间也存在。若区间结束值一样，则把开始值大的排前面，这样下个区间肯定覆盖了上个区间

② .取值

为使当前区间取的值更可能在下个区间也存在，原则上每个区间都取末尾两个元素值。 按以上规则排序后，遍历每个区间进行判断，判断当前取值结果的末尾两个元素是否在当前区间内包含，根据结果添加新的元素：

若两个元素都在当前区间包含，则不需要添加新元素 若只有一个元素在当前区间包含，则添加当前区间的末尾一个元素 若两个元素都不在当前区间包含，则添加当前区间的末尾两个元素

代码示例

class Solution {
          
   
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
          
   
        int size = intervals.size();
        sort(intervals.begin(),intervals.end(),[&](vector<int> &a,vector<int> &b){
          
   
            if( a[1] == b[1] ) //相同结尾
            {
          
   
                return a[0] >b[0] ;//范围更小的排前面
            }
            return a[1] < b[1] ;//结束值越小的排前面
        });

        vector<int> res;
        res.push_back(intervals[0][1]-1);//
        res.push_back(intervals[0][1]);//初始把第一个区间的末尾两个字添加上

        for( auto & vec : intervals )
        {
          
   
            int cur_size = res.size();
            if( vec[0] <= res[cur_size-2] ) //起始值小于倒数第 2 个元素，肯定满足
            {
          
   
                continue;
            }
            if( vec[0] <= res[cur_size-1] )//交集仅满足一个值
            {
          
   
                res.push_back(vec[1]);//把末尾值加进来
            }
            else//没有交集
            {
          
   
                res.push_back(vec[1]-1);//
                res.push_back(vec[1]);//把末尾两个值加进来
            }
        }
        return res.size();
    }
};