Insert Interval

Given a list of non-overlapping intervals sorted by start, insert a new interval and merge if necessary.

Why this is worth learning

The input already supplies the sorted disjoint structure that Merge Intervals would otherwise have to build. Exploit it with before, overlapping, and after phases.

Before coding: one-minute experiment

Insert [2,8] into [[1,2],[4,5],[8,10]]. What remains?

Function signature

func InsertInterval(intervals [][]int, newInterval []int) [][]int

Inputs / outputs

• intervals: sorted, non-overlapping intervals.
• newInterval: interval to insert.
• Return: updated list of merged intervals.

Example

intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Constraints

• 0 <= len(intervals) <= 100_000
• -1_000_000_000 <= start <= end <= 1_000_000_000

Core idea (near-solution)

Split intervals into three parts:

1. Intervals completely before the new interval.
2. Intervals overlapping the new interval.
3. Intervals completely after the new interval.

Merge the overlapping ones into newInterval, then concatenate.

Algorithm (step-by-step)

1. Append all intervals that end before newInterval starts.
2. Merge all intervals that overlap newInterval, adjusting its start/end.
3. Append the merged newInterval.
4. Append the remaining intervals.

Correctness sketch

Intervals ending before the new start are disjoint and can be copied directly to output. Thereafter, while a next start is at most the growing merged end, it overlaps the new component; widening start and end to the minimum and maximum preserves that component's exact union. Once a next start exceeds the merged end, sortedness proves every remaining interval is disjoint and later, so the merged interval is final. Appending the untouched suffix completes the union in order. The phases cover every old interval exactly once and insert exactly one merged component, including when the original list is empty.

Trace (hand walkthrough)

Example input:
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Walk:
- new [2,5] overlaps [1,3] -> merge to [1,5]
- append remaining [6,9] -> [[1,5],[6,9]]

Pitfalls to avoid

• Forgetting to append intervals after the merge.
• Incorrect overlap check (interval.start <= newEnd).

Debugging lens

Test an insertion before everything, after everything, wholly inside one interval, and spanning every interval. Do not sort again or mutate newInterval unless the contract explicitly requires it.

Complexity

• Time: O(n)
• Extra space: O(n) for output.

Implementation notes (Go)

• Append intervals that end before the new interval starts.
• Merge overlaps, then append remaining intervals.

Contract precision

Input intervals are sorted and pairwise disjoint as closed intervals. The supplied implementation does not mutate either input, but unmerged rows in its result can share backing arrays with the input rows.

Reconstruction checkpoint

Insert [2,8] into [[1,2],[4,5],[8,10]]. What remains?

Return to Intervals · Module quiz