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

# Insert Intveral

Merge Intervals

## Problem

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.

{% hint style="info" %}
For example:

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

Output: [[1,5],[6,9]]
```

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

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

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

{% endhint %}

### Thought Process

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MNPhzQdDSv0oZZktWwL%2F-MNPoQBz1LbsnjWpdLYn%2FIMG_273F20C3FF46-1.jpeg?alt=media\&token=cb0e13c8-2fcd-4b10-a818-ca9b8ec859af)

## Solution

```
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        i, start, end = 0,0,1
        
        #finding interval where interval[i].end >= newInterval[start]
        while i < len(intervals) and newInterval[start] > intervals[i][end]:
            res.append(intervals[i])
            i+=1
            
        #if interval[start] is less than newInterval[end] this means we can merge
        #We borrowing "intervals[i][start] <= newInterval[end]" from Merge Interval
        while i < len(intervals) and intervals[i][start] <= newInterval[end]:
            newInterval[start] = min(newInterval[start], intervals[i][start])
            newInterval[end] = max(newInterval[end], intervals[i][end])
            i+=1
        
        res.append(newInterval)
        
        while i < len(intervals): #place the rest of the intervals
            res.append(intervals[i])
            i+=1
        return res
        
#Time: O(n)
#Space: O(n)
```