---
# System prepended metadata

title: LC 57. Insert Interval
tags: [medium, leedcode, c++]

---

# 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<sub>i</sub>, end<sub>i</sub>]</code> represent the start and the end of the <code>i<sup>th</sup></code> interval and <code>intervals</code> is sorted in ascending order by <code>start<sub>i</sub></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<sub>i</sub></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<sup>4</sup></code>
- <code>intervals[i].length == 2</code>
- <code>0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>5</sup></code>
- <code>intervals</code> is sorted by <code>start<sub>i</sub></code> in  **ascending**  order.
- <code>newInterval.length == 2</code>
- <code>0 <= start <= end <= 10<sup>5</sup></code>

## Solution 1
#### C++
```cpp=
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)
