See all coding puzzles and patterns here.

Problem Definition

Given an array of non-overlapping intervals of form [start, end] that have been sorted by their start and an additional interval, insert the interval into the array of non-overlapping intervals while preserving the order of the array and ensuring that the resultant array of intervals are all non-overlapping.

Examples

Some test cases to verify our solution.


assert(insert_interval([[1,3],[6,9]], [2,5]) == [[1,5],[6,9]])
assert(insert_interval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]) == [[1,2],[3,10],[12,16]])

Linear Search Solution

We look through the existing intervals until we find the place where the new interval should be inserted or merged into an existing interval. From there, we insert the new interval and merge it with the existing intervals until a non-overlapping interval is encountered. Then we append the remainder of the intervals to the result. 

def insert_interval(intervals: list[list[int]], newInterval: list[int]) -> None:
    if not intervals:
        return [newInterval]
    start, end = newInterval
    n = len(intervals)
    res = []
    i = 0
    while i < n and intervals[i][1] < start:
        res.append(intervals[i])
        i += 1
    while i < n and end >= intervals[i][0]:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    res.append([start, end])
    while i < n:
        res.append(intervals[i])
        i += 1
    return res

Linear Search Solution Complexity

Let $n = $ len(intervals).

Runtime complexity should be $\Theta(n)$ since we will look at every interval once.

Auxiliary space complexity should be $O(1)$ since res, our only non-scalar variable, is our return value.