C++每日一练16-插入区间

插入区间 给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）

class Solution {
          
   
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
          
   //11
        vector<vector<int>> res;
        vector<int> newIns;
        int flag = 0;
        if (intervals.empty()) {
          
   
            res.emplace_back(newInterval);//原区间为空
            return res;
        }
        if (newInterval.empty()) {
          
   
            return res;//插入区间为空
        }
        for (vector<int> itl1 : intervals) {
          
   
            if (itl1.back() < newInterval.front() || flag == 2)
                res.emplace_back(itl1);//不满足插入插入条件的小区间或者已经完成插入操作后的区间
            else {
          
   
                if (flag == 1) {
          
   //插入区间最终的左边界已经确定
                    if (itl1.front() <= newInterval.back())
                        if (itl1.back() < newInterval.back()) {
          
   //最终区间包含的区间，舍去
                            if (itl1 == intervals.back()) {
          
   //如果之确定了左边界，但右边界未确定，又是最后一个元素，那么该区间就是最终插入区间
                                res.emplace_back(newInterval);
                                flag++;
                                continue;
                            }
                            continue;
                        }
                        else {
          
   
                            //确定右边界
                            newInterval.back() = itl1.back();
                            res.emplace_back(newInterval);
                            flag++;
                            continue;
                        }
                    else {
          
   
                        //此情况为插入区间的尾元素小于原来区间的首元素
                        res.emplace_back(newInterval);
                        res.emplace_back(itl1);
                        flag++;
                        continue;
                    }
                }
                if (flag == 0 && newInterval.front() >= itl1.front()) {
          
   //确定左边界
                    newInterval.front() = itl1.front();
                    flag++;
                }
                else {
          
   
                    //此情况为插入区间左区间小于所需插入的原来小区间的左边界，无需修改
                    flag++;
                }
                if (newInterval.back() < itl1.front()) {
          
   
                    //此情况为原来区间只有一个元素，并且插入区间的右边界小于原来区间唯一元素的左边界
                    res.emplace_back(newInterval);
                    res.emplace_back(itl1);
                    flag = 2;
                    continue;
                }
                if (itl1.back() >= newInterval.back()) {
          
   
                    //修改插入左边界后，原来小区间对应的右边界会包含插入区间的右边界
                    newInterval.back() = itl1.back();
                    res.emplace_back(newInterval);
                    flag++;
                }
                else if (itl1 == intervals.back()) {
          
   
                    res.emplace_back(newInterval);
                }
            }
        }
        if (flag == 0) res.emplace_back(newInterval);
        return res;
    }
};

复杂度分析

时间复杂度：O(n)