57. Insert Interval

Given an array of non-overlapping intervals intervals which is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.

Note: I struggled a lot with edge cases.

def insert(self, intervals: List[List[int]], newInterval: List[int]):

       

    output = []

    L = len(intervals)        

   

    i = 0

    while i < L and intervals[i][0] < newInterval[0]:

        output.append(intervals[i])

        i += 1

       

    if not output or output[-1][1] < newInterval[0]:

        output.append(newInterval)

    else:

        output[-1][1] = max(output[-1][1], newInterval[1])

   

    while i < L:

        interval = intervals[i]

       

        if interval[0] <= output[-1][1]:

            output[-1][1] = max(output[-1][1], interval[1])

        else:

            output.append(interval)        

        i += 1

               

    return output