## [57\. Insert Interval](https://leetcode.com/problems/insert-interval/)

You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [starti, endi]` represent the start and the end of the `ith` interval and `intervals` is sorted in ascending order by `starti`. You are also given an interval `newInterval = [start, end]` that represents the start and end of another interval.

Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `starti` and `intervals` still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return `intervals`_ after the insertion_.

**Note** that you don't need to modify `intervals` in-place. You can make a new array and return it.

**Example 1:**

**Input:** intervals = \[\[1,3\],\[6,9\]\], newInterval = \[2,5\]
**Output:** \[\[1,5\],\[6,9\]\]

**Example 2:**

**Input:** intervals = \[\[1,2\],\[3,5\],\[6,7\],\[8,10\],\[12,16\]\], newInterval = \[4,8\]
**Output:** \[\[1,2\],\[3,10\],\[12,16\]\]
**Explanation:** Because the new interval \[4,8\] overlaps with \[3,5\],\[6,7\],\[8,10\].

**Constraints:**

- `0 <= intervals.length <= 104`
- `intervals[i].length == 2`
- `0 <= starti <= endi <= 105`
- `intervals` is sorted by `starti` in **ascending** order.
- `newInterval.length == 2`
- `0 <= start <= end <= 105`

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res;
        res.push_back(intervals[0]);
        // intervals = [[1, 3], [2, 5], [6, 9]]
        for(int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] <= res.back()[1]) {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            } else {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

:::success
- 時間複雜度：$O(N \cdot \log N)$
- 空間複雜度：$O(N)$
:::

Binary Search

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        if(n == 0) return {newInterval};
        
        // Binary Search 尋找要插入的區間
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (intervals[mid][0] < newInterval[0]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // 插入區間
        intervals.insert(intervals.begin() + left, newInterval);
        
        // 處理重疊區間        
        vector<vector<int>> res;
        for (auto& interval : intervals) {
            if (res.empty() || res.back()[1] < interval[0]) {
                res.push_back(interval);
            } else {
                res.back()[1] = max(res.back()[1], interval[1]);
            }
        }
        return res;
    }
};

:::success
- 時間複雜度：$O(N + \log N)$
- 空間複雜度：$O(N)$
:::