Insert Interval

Instructions

Insert newInterval into intervals such that intervals is still sorted in ascending order and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Attempt here

Example

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

Approach

Since the input is sorted, we can check if the end value of newInterval is less than the start value of the elements in the intervals list.

If the endtime of the newInterval is less than start[i][0] then we insert it in the results variable then insert the remaining intervals because output should be in ascending order.

If the starttime of the newInterval is greater than the endtime of a given interval then we append the interval to the results

For overlapping intervals, we merge them by geting the start value as the minimum of the two starts and the end value as the maximum of the end values.
Append new interval to result and return result.

Implementation

def insert(intervals, newInterval):

        result = []
        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                result.append(newInterval)
                return result + intervals[i:]
            elif newInterval[0] > intervals[i][1]:
                result.append(intervals[i])
            else:
                newInterval = [min(newInterval[0],intervals[i][0]), max(newInterval[1],intervals[i][1])]

        result.append(newInterval)

        return result

This runs in O(n) time complexity and O(n) space complexity.

Happy learning!!