# 0057. Insert Interval
###### tags: `Leetcode` `Medium`
## 思路
这道题和上一道题不一样的地方是，这一道题的input已经排好顺序了，同时，是互不相交的interval，因此我们只需要考虑所给的需要insert的interval，应该和输入的interval集合里面的哪些merge起来就可以了。

有非常多edge case 但java的写法巧妙避开了edge case 所以要重点掌握思路

但C++的思路也可以借鉴

因为已经知道要用回圈一个个做判断，看看given interval能和谁并列，我觉得这道题的很巧妙并且值得注意的地方就是：1.条件判断，不需要分成8种情况，只要分成**要插入左边且无交集**、**要插入右边且无交集**、**有交集**即可。2. 56题的时候，当结果里的最后一个的右边界大于现在的interval的左边界时（意味着结果里的最后一个要和现在的interval合并），那么将最后一个pop出来，合并完再push回去，而这边才用了用**两个变量left，right**记录的方法，当确认好，[left,right]不再需要和别人merge的时候，再push进去。

## Code

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new ArrayList<>();
        int idx = 0;
        while(idx<intervals.length && intervals[idx][1]<newInterval[0]){
            ans.add(intervals[idx++]);
        }
        int l = newInterval[0], r=newInterval[1];
        while(idx<intervals.length && intervals[idx][0]<=newInterval[1]){
            l = Math.min(l, intervals[idx][0]);
            r = Math.max(r, intervals[idx][1]);
            idx++;
        }
        ans.add(new int[]{l,r});
        while(idx<intervals.length){
            ans.add(intervals[idx++]);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        if(intervals.size()==0){
            ans.push_back(newInterval);
            return ans;
        }
        int left = newInterval[0];
        int right = newInterval[1];
        //用两个变量比一直pop push好很多
        bool placed = false;
        for(int i = 0; i < intervals.size(); i++){
            //被分的情况越少越好 无交集则代表之后也不用再考虑了
            //插入左边且无交集
            if(right<intervals[i][0]){
                if(!placed){
                    ans.push_back({left,right});
                    placed = true;
                }
                ans.push_back(intervals[i]);
            }
            else if(left > intervals[i][1]){
                ans.push_back(intervals[i]);
            }
            else{//有交集
                left = min(intervals[i][0],left);
                right = max(intervals[i][1],right);
            }
        }
        if(!placed){
            ans.push_back({left,right});
        }
        return ans;
    }
};