57. Insert Interval

解題思路

在 traverse 給定的 intervals 時，要思考的是：newInterval 是否與之重疊、或會插在哪裡？

而可以想像的是，當有兩個 intervals 時，關於重疊只會有三種情形：newInterval 要放 interval 左邊、放右邊，或者兩個重疊要 merge。

情況一：放左邊

這種情況代表要插入整個 intervals  的最前面。

情況二：放右邊

這種情況代表沒有重疊到，只是放入 intervals 中。

情況三：merge

如果既不屬於左邊也不屬於右邊，那就要把當前 interval 跟 newInterval  merge起來。merge 取兩端點最小與最大即可。

程式碼

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        
        for(int i=0; i<intervals.size(); i++)
        {
            if(newInterval[1] < intervals[i][0])
            {
                ans.push_back(newInterval);
                newInterval = intervals[i];
            }
            else if(newInterval[0] > intervals[i][1])
            {
                ans.push_back(intervals[i]);
            }
            else
            {
                newInterval[0] = min(intervals[i][0], newInterval[0]);
                newInterval[1] = max(intervals[i][1], newInterval[1]);
            }
        }
        ans.push_back(newInterval);
        return ans;
    }
};