## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Insert Interval

Problem Statement
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

```from typing import List

class Solution:
def insert(self, intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
if len(intervals) == 0:
return [new_interval]

result = []

i = 0
# Add all intervals that start and end before the new_interval
for interval in intervals:
if interval[1] < new_interval[0]:
result.append(interval)
i += 1
else:
break

#  Merge all intervals that overlap with the new_interval
while i < len(intervals):
if intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
else:
break
i += 1

result.append(new_interval)

result += intervals[i:]

return result

def main():
solution = Solution()
result = solution.insert(intervals=[[1, 3], [6, 9]], new_interval=[2, 5])
print(f"Result {result}")

# [[1,5],[6,9]]

result = solution.insert(intervals=[[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new_interval=[4, 8])
print(f"Result {result}")
# [[1, 2], [3, 10], [12, 16]]

result = solution.insert(intervals=[], new_interval=[5, 7])
print(f"Result {result}")

result = solution.insert(intervals=[[1, 5]], new_interval=[2, 3])
print(f"Result {result}")

result = solution.insert(intervals=[[1, 5]], new_interval=[0, 3])
print(f"Result {result}")

result = solution.insert(intervals=[[1, 5]], new_interval=[0, 0])
print(f"Result {result}")

if __name__ == "__main__":
main()

```