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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        

Solutions:
class Solution:

	def insert(self, intervals, newInterval):
		start = len(intervals)
		for i in range(len(intervals)):
			if newInterval.start < intervals[i].start:
				start = min(start, i)
			if not (newInterval.start > intervals[i].end or newInterval.end < intervals[i].start):
				newInterval = Interval(min(newInterval.start, intervals[i].start), max(newInterval.end, intervals[i].end))
				(start, intervals[i]) = (min(i, start), [])
		intervals = [ele for ele in intervals if ele != []]
		intervals.insert(start, newInterval)
		return intervals