# 57 - Insert Interval

解法一 - 暴力法

我們可以直接把 newInterval append 到 intervals，然後做跟 #56 一樣的事，但是這樣的時間複雜度是 O(NlogN)，浪費了原本 intervals 就是 sorted 的這個性質。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);

        sort(intervals.begin(), intervals.end(), [](const vector<int>& i1, const vector<int>& i2) {
            return i1[0] < i2[0];
        });

        vector<vector<int>> res = {intervals[0]};

        for(int i = 1; i < intervals.size(); ++i) {
            if(res.back()[1] < intervals[i][0]) {
                res.push_back(intervals[i]);
            }    
            else {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
        }

        return res;
    }
};

解法二 - 只 merge 需要 merge 的 interval

因為 intervals 已經是 sorted，所以我們可以排除掉 end 比 newInterval.start 還要早的所有 interval，然後遇到第一個 end 比 newInterval.start 早的 interval，我們就可以開始 merge。

下面的說明很好地總結了幾種 overlap 的形式：

程式碼如下：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int i = 0;

        // Skipping all intervals which ends before newInterval starts
        vector<vector<int>> res;
        while(i < intervals.size() && intervals[i][1] < newInterval[0]) {
            res.push_back(intervals[i]);
            ++i;
        }

        // Keep merging until intervals[i] starts after newInterval 
        while(i < intervals.size() && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            ++i;
        }
        res.push_back(newInterval);

        // Push all left inter
        while(i < intervals.size()) {
            res.push_back(intervals[i]);
            ++i;
        }

        return res;
    }
};

Runtime: 16 ms, faster than 82.65% of C++ online submissions for Insert Interval. Memory Usage: 12.2 MB, less than 100.00% of C++ online submissions for Insert Interval.