LeetCode 57. 插入区间

LeetCode 57. 插入区间
思路：
把区间分为三个部分，中间的部分是与新加入的区间合并的部分，我们只要维护好中间的部分就可以了。

代码

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n=intervals.size();
        vector<vector<int>> res;

        int l=newInterval[0];
        int r=newInterval[1];

        int i=0;

        while(i<n && intervals[i][1] < l) res.push_back({intervals[i][0], intervals[i++][1]});

        //中间的部分

        while(i<n && intervals[i][0] <= r){
            l=min(l,intervals[i][0]);
            r=max(r,intervals[i++][1]);
        }

        res.push_back({l,r});

        //后半部分

        while(i<n) res.push_back({intervals[i][0],intervals[i++][1]});

        return res;
    }
};