【Leetcode贪心区间问题六】56. 合并区间

• Leetcode56
• • 1.问题描述
  • 2.解决方案
  • • 解法一：
    • 解法二：
    • 总结解法一和解法二的两点不同：

这道题呢和452. 用最少数量的箭引爆气球 中的解法一很相似，可以说就基本一样的解题思路
1.维护一个temp，当找到一个和temp不重叠的区间时，我们会把temp加入结果集，并且更新temp为找到的这个区间，如果有重叠那就更新temp为并集，不加入结果集
2.循环结束别忘了把最后一个temp加入结果集

class Solution {
public:
    static bool cmp(vector& a,vector& b){
        //按区间左边界排序
        return a[0]> merge(vector>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        vector> ans;
        vector temp=intervals[0];
        for(int i=1;itemp[1]){
                ans.push_back(temp);
                temp=intervals[i];
            }
            //交叉
            if(intervals[i][0]<=temp[1]){
                //[1,6] [2,5] 包含
                if(intervals[i][1]<=temp[1]){
                    continue;
                }
                //[1,6] [2,7] 交叉
                if(intervals[i][1]>temp[1]){
                    //temp=[1,7]
                    temp=vector{temp[0],intervals[i][1]};
                }
            }
        }
        ans.push_back(temp);
        return ans;
    }
};

思路呢和解法一其实差不多，和452. 用最少数量的箭引爆气球 中的解法二很相似
1.解法二相对于解法一呢，不维护temp，每次遍历到的区间和结果集的back()比较就好了
2.找到一个不交叉的就直接加入结果集
3.找到一个有交叉的也好办，直接更新为更大的那个右边界：
ans.back()[1]=max(ans.back()[1],intervals[i][1]);
4.当然为了代码简洁cmp函数用到了一个Lambda表达式

class Solution1 {
public:
    vector> merge(vector>& intervals) {
        sort(intervals.begin(),intervals.end(),[](const vector& a,const vector& b){return a[0]> ans;
        ans.push_back(intervals[0]);

        for(int i=1;ians.back()[1]){
                ans.push_back(intervals[i]);
            }
            //交叉[1,6] [2,5]或[1,6] [2,7]
            if(intervals[i][0]<=ans.back()[1]){
                ans.back()[1]=max(ans.back()[1],intervals[i][1]);
            }
        }
        return ans;
    }
};

1.解法一维护了temp,而解法二直接加入结果集每次跟结果集的最后一个区间比较
2.当遇到交叉的情况时不需要分情况是包含还是相交，直接取两个区间右边界较大的那个就好