# LC 57. Insert Interval

### [Problem link](https://leetcode.com/problems/insert-interval/)

###### tags: `leedcode` `medium` `c++`

You are given an array of non-overlapping intervals <code>intervals</code> where <code>intervals[i] = [start_i, end_i]</code> represent the start and the end of the <code>i^th</code> interval and <code>intervals</code> is sorted in ascending order by <code>start_i</code>. You are also given an interval <code>newInterval = [start, end]</code> that represents the start and end of another interval.

Insert <code>newInterval</code> into <code>intervals</code> such that <code>intervals</code> is still sorted in ascending order by <code>start_i</code> and <code>intervals</code> still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return <code>intervals</code> after the insertion.

**Note** that you don't need to modify <code>intervals</code> 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:**

- <code>0 <= intervals.length <= 10⁴</code>
- <code>intervals[i].length == 2</code>
- <code>0 <= start_i <= end_i <= 10⁵</code>
- <code>intervals</code> is sorted by <code>start_i</code> in **ascending** order.
- <code>newInterval.length == 2</code>
- <code>0 <= start <= end <= 10⁵</code>

## Solution 1
#### C++

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int start = newInterval[0];
        int end = newInterval[1];
        vector<vector<int>> ans;
        int i = 0;

        while (i < intervals.size() && intervals[i][1] < start) {
            ans.push_back(intervals[i]);
            i++;
        }

        while (i < intervals.size() && intervals[i][0] <= end) {
            start = min(start, intervals[i][0]);
            end = max(end, intervals[i][1]);
            i++;
        }
        ans.push_back({start, end});

        while (i < intervals.size()) {
            ans.push_back(intervals[i]);
            i++;
        }
        return ans;
    }
};

>### Complexity
>n = intervals.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
sol1:
第一個while: 找到重疊前的最後一個interval.
第一個while: 所有intervals[1] <= end的都有可能與newInterval重疊.
第二個while: 之後的都不可能與newInterval重疊, 所以直接加到ans就好.

Space Complexity: 忽略return value的話是O(1)