CodeEasy v0.1

Insert Interval

Medium Subject: Intervals
Time Complexity
O(N)
Space Complexity
O(N)

Problem Description

You are given an array of non-overlapping intervals sorted by start time, and a new interval. Insert the new interval into the array, merging if necessary.

Optimal Solution

Python 
def insert(intervals, newInterval):
    res = []
    i, n = 0, len(intervals)
    # add all intervals ending before newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        res.append(intervals[i])
        i += 1
    # merge overlapping intervals
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    res.append(newInterval)
    # add remaining
    while i < n:
        res.append(intervals[i])
        i += 1
    return res