【力扣每日一题】2023.8.28 插入区间-Toy模板网

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

题目：

示例：

分析：

代码：

题目：

【力扣每日一题】2023.8.28 插入区间,力扣每日一题,leetcode,算法,数据结构,c++

示例：

【力扣每日一题】2023.8.28 插入区间,力扣每日一题,leetcode,算法,数据结构,c++

分析：

和昨天的题大差不差，我们仍然是有一堆区间，题目给我们一个新的区间，要我们把新区间插入到原本的区间数组里，并且能合并的要合并。

我们可以直接把新区间放入数组里，接着执行昨天的代码即可，一行都不用改，甚至形参名字都是一样的。

由于本题中原始数组就是按照左区间升序排序，因此我们可以做一个小优化，我们按照左区间升序的这样一个规则插入新区间，这样就不必再对数组进行排序从而减少运行时间了。我们只需要找到原始区间中第一个左区间大于新区间的左区间的区间即可，然后将新区间插入到这个区间的前面，接着再按照昨天的代码。文章来源地址https://www.toymoban.com/news/detail-684635.html

代码：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        //昨天的代码照搬
        intervals.push_back(newInterval);
        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;

        //小小优化一下
        int index=0;
        for(;index<intervals.size();index++){
            if(newInterval[0]<=intervals[index][0]) break;
        }
        intervals.insert(intervals.begin()+index,newInterval);
        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.28 插入区间的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！