> For the complete documentation index, see [llms.txt](https://zhongquan789.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongquan789.gitbook.io/leetcode/leetcode/leetcode_57.md).

# leetcode\_57

## 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:

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].
```

## NOTE:

input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

## Solutions

1. **straight forward**
2. Collect intervals don't overlap with the newInterval.
   * collect intervals whose end is smaller than inserted interval' start.
   * collect intervals whose start is larger than inserted interval's end.
3. Merge overlapping intervals by finding the minimum start and the maximum end among them.
   * Choose the smallest between inserted intervals's start and the first overlapped interval's start as the start.
   * The same for choosing the end as the end.
   * Finally build a new interval with the start and end.
4. Concatenate these three parts.

```cpp
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<int> left, merged, right;
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals[i][1] < newInterval[0])
                left.push_back(i);
            else if (intervals[i][0] > newInterval[1])
                right.push_back(i);
            else
                merged.push_back(i);
        }

        vector<vector<int>> res;
        for (int i : left)
            res.push_back(intervals[i]);
        int st = newInterval[0], ed = newInterval[1];
        if (merged.size()) {
            st = min(intervals[merged.front()][0], st);
            ed = max(intervals[merged.back()][1], ed);
        }
        res.push_back({st, ed});
        for (int i : right)
            res.push_back(intervals[i]);

        return res;
    }
};
```

```python
class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        alls = merged, left, right = [], [], []
        s, e = newInterval
        for i in intervals:
            alls[(i[1] < s) - (i[0] > e)].append(i)
        if merged:
            s = min(merged[0][0], s)
            e = max(merged[-1][1], e)
        return left + [[s, e]] + right
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhongquan789.gitbook.io/leetcode/leetcode/leetcode_57.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.