> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/arrays/35.-insert-interval.md).

# 35. Insert Interval

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

**Example 3:**

```
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
```

**Example 4:**

```
Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]
```

**Example 5:**

```
Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]
```

## Solution: 

**Insert and Merge**

```cpp
class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {

        int i = 0;

        while (i < intervals.size())
        {
            if (intervals[i][0] >= newInterval[0])
            {
                break;
            }
            i++;
        }

        intervals.insert(intervals.begin() + i, newInterval);

        vector<vector<int>> res;
        int idx = 0;

        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] <= intervals[idx][1])
            {
                intervals[idx][0] = min(intervals[i][0], intervals[idx][0]);
                intervals[idx][1] = max(intervals[i][1], intervals[idx][1]);
            }
            else
            {
                res.push_back({intervals[idx][0], intervals[idx][1]});
                idx = i;
            }
        }

        res.push_back({intervals[idx][0], intervals[idx][1]});

        return res;
    }
};
```

**Time Complexity: O(n)**