【力扣每日一题】2023.8.27 合并区间-Toy模板网

这篇具有很好参考价值的文章主要介绍了【力扣每日一题】2023.8.27 合并区间。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

示例：

分析：

代码：

题目：

【力扣每日一题】2023.8.27 合并区间,力扣每日一题,leetcode,算法,c++,数据结构

示例：

【力扣每日一题】2023.8.27 合并区间,力扣每日一题,leetcode,算法,c++,数据结构

分析：

那么合并区间是在什么情况下才能合并呢？

我总结为两种情况

第一种情况就是这样，第二个区间的左区间大于第一个区间的左区间但是小于第一个区间的右区间，并且第一个区间的右区间小于第二个区间的右区间，这种情况下合并的结果就是第一个区间的左区间和第二个区间的右区间组成一个新的更大的区间。

【力扣每日一题】2023.8.27 合并区间,力扣每日一题,leetcode,算法,c++,数据结构

第二种情况就是第二个区间的左区间大于第一个区间的左区间但是小于第一个区间的右区间，并且第一个区间的右区间大于第二个区间的右区间，这种情况下合并的结果就是第一个区间把第二个区间吞并。

【力扣每日一题】2023.8.27 合并区间,力扣每日一题,leetcode,算法,c++,数据结构

以上两种情况都是基于第一个区间的左区间小于第二个区间的左区间的，所以我们可以先对给的区间按照左区间进行排序。

昨天是汇总区间，今天是合并区间，我们和昨天一样的是需要两个变量来记录左右区间，并且初始化为第一个区间，从下标为1的位置往后遍历剩余区间。

如果当前遍历到的区间的左区间小于等于临时变量的右区间，那么可以合并区间，我们把临时变量的右区间更新为较大值。

如果当前遍历到的区间的左区间大于临时变量的右区间，那么我们无法再合并区间了，我们往答案中添加临时变量组成的区间，然后更新临时变量为当前区间。

【力扣每日一题】2023.8.27 合并区间,力扣每日一题,leetcode,算法,c++,数据结构文章来源地址https://www.toymoban.com/news/detail-675449.html

代码：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),[](vector<int>a,vector<int>b){return a[0]<b[0];});
        vector<vector<int>>res;
        int begin=intervals[0][0],end=intervals[0][1];  //临时变量记录左右区间,初始化为数组第一个元素
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]>end){    //如果新区间的左区间大于临时的右区间,则发生区间不重合
                res.push_back({begin,end}); //添加临时变量的区间
                begin=intervals[i][0],end=intervals[i][1];  //更新两个临时变量
            }else{
                end=max(end,intervals[i][1]);   //如果区间重合,那么更新临时变量的右区间为较大值
            }
        }
        res.push_back({begin,end});
        return res;
    }
};

到了这里，关于【力扣每日一题】2023.8.27 合并区间的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！