> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/intervals/insert-interval.md).

# Insert Interval

<https://leetcode.com/problems/insert-interval/description/>

> Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
>
> You may assume that the intervals were initially sorted according to their start times.
>
> Example 1:
>
> Given intervals \[1,3],\[6,9], insert and merge \[2,5] in as \[1,5],\[6,9].
>
> Example 2:
>
> Given \[1,2],\[3,5],\[6,7],\[8,10],\[12,16], insert and merge \[4,9] in as \[1,2],\[3,10],\[12,16].
>
> This is because the new interval \[4,9] overlaps with \[3,5],\[6,7],\[8,10].

## Thoughts

intervals分为三段, 第一段end都在newInterval前, 第二段interval.start 都在newInterval.end前, 和newInterval有overlapping, 把interval不断合并到newInterval中, 第三段是剩下的.

## Code

```
/*
 * @lc app=leetcode id=57 lang=cpp
 *
 * [57] Insert Interval
 */
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int N = intervals.size(), i = 0;
        for (; i < N; ++i) {
            if (intervals[i][1] < newInterval[0]) res.push_back(intervals[i]);
            else break;
        }
        for (; i < N; ++i) {
            if (newInterval[1] < intervals[i][0]) break;
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
        }
        res.push_back(newInterval);
        for (; i < N; ++i) {
            res.push_back(intervals[i]);
        }
        return res;
    }
};


```

## Analysis

时间复杂度O(N).