# 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) # Add the remaining intervals 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()