Insert Interval

Intuition

Since the list is already sorted and gap-free, every interval falls into exactly one of three buckets relative to the new interval: strictly before it, overlapping it, or strictly after it. We handle the buckets in order. First we pass along the intervals that end before the new start. Next we widen the new interval by pulling in the min start and max end of anything that overlaps. Finally we drop in the merged new interval and copy whatever remains.

Algorithm walkthrough

1. 1Walk from the left, appending each interval whose end is smaller than the new interval's start.
2. 2While the current interval's start is not past the new interval's end, expand the new interval's start down and end up to swallow it.
3. 3Append the fully expanded new interval to the result.
4. 4Append every remaining interval, all of which start after the new interval ends.
5. 5Return the assembled result list.

Implementation

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