1、题目

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

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

链接：https://leetcode-cn.com/problems/insert-interval/
 

2、思路分析

1）模拟
遍历原数组，更新left和right的值，插入到新数组中。

三种情况，第一种：要插入的右小于当前的左，如果还没插入，则将其插入到新数组中
第二种：如果当前的右小于要插入的左，则将当前的值插入到新数组中
第三种：含有交集，更新left和right（因为之后可能左右值不是现在的，所以不能现在插入）
最后在遍历完成之后，如果还没插入，则将其插入到新数组中。

注意：在将newInterval插入之后，需要将placed设置为true，表示已经插入，不能重复插。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        bool placed = false; // 用placed表示这个要插入的数字只能插入一次
        vector<vector<int>> ans;
        for(const auto interval : intervals){
            if(interval[0] > right){ // 这种是已经过了要插入的地方
                if(!placed){
                    ans.push_back({left, right});
                    placed = true; // 需要及时更改
                }
                ans.push_back(interval);            
            }
            else if(interval[1] < left){ // 这种是还没到要插入的地方
                ans.push_back(interval);
            }
            else {
                // 这种情况就是交集
                left = min(left, interval[0]);
                right = max(right, interval[1]);
            }
        }
        if(!placed){
            ans.push_back({left, right});
        }
        return ans;
        // 这种不用考虑怎么更改每个区间的left，right，这种只用可以更新left和right的值，最后没有插入的时候，将其插入进去
    }
};