Insert Interval

Insert one range into sorted, non-overlapping ranges and merge when needed.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Insert Interval: Partition sorted ranges into a copied prefix, one growing overlap span, and an untouched suffix.

Input and goalInsert one range into sorted, non-overlapping ranges and merge when needed.

Initialize the inserted rangeUse intervals [[1,2],[3,5],[6,7],[8,10],[12,16]] and new [4,8]. Start answer = [], index = 0, span = [4,8].

current [1,2]

[3,5]

new span [4,8]

[6,7]

[8,10]

[12,16]

stateanswer = []; span = [4,8]

Recognize it

Use it when inserting one range into already sorted disjoint ranges; their order partitions them into intervals ending before, overlapping, or starting after the growing span.

Keep true

answer contains every interval strictly before the span, span is the union of the new interval and all consumed overlaps, and intervals from index onward remain untouched and sorted.

Reuse it

When ordered input surrounds one mutable object, scan an immutable prefix, absorb the contiguous interaction region into that object, then reuse the untouched suffix.

Pattern: Three interval groups.

Simple idea: First copy ranges fully before the new range. Then merge every overlap. Finally copy the ranges fully after it.

def insert_interval(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
   answer: list[list[int]] = []
   index = 0
   start, end = new_interval

   while index < len(intervals) and intervals[index][1] < start:
      answer.append(intervals[index])
      index += 1

   while index < len(intervals) and intervals[index][0] <= end:
      start = min(start, intervals[index][0])
      end = max(end, intervals[index][1])
      index += 1

   return answer + [[start, end]] + intervals[index:]

Cost: $O(n)$ time and $O(n)$ answer space.