Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represents the start and the end time of the ith interval. intervals is initially sorted in ascending order by start_i.

You are given another interval newInterval = [start, end].

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and also intervals still does not have any overlapping intervals. You may merge the overlapping intervals if needed.

Return intervals after adding newInterval.

Note: Intervals are non-overlapping if they have no common point. For example, [1,2] and [3,4] are non-overlapping, but [1,2] and [2,3] are overlapping.

Approach

Scan intervals in order. Add all intervals that end before the new interval starts. Then merge any overlapping intervals with the new interval by expanding its bounds. Finally, append the merged interval and the remaining intervals.

Why It Works

Intervals are processed in sorted order, so once an interval starts after the current merged interval ends, there can be no future overlaps. Merging all overlaps into the new interval ensures the result is non-overlapping and sorted.

Complexity

• Time: O(n)
• Space: O(n) for the output

Reference Implementation (Python)

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        i = 0
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1

        result.append(newInterval)
        result.extend(intervals[i:])
        return result