Insert Interval

Non-overlapping Intervals

Excel Sheet Column Number

Insert one interval into sorted disjoint intervals and merge any overlaps.

Given a sorted list of non-overlapping intervals `intervals` and one additional interval `new_interval`, insert the new interval into the correct position and merge every overlap created by that insertion. Return the resulting intervals in sorted order.

## Example
```
Input: {"intervals":[[1,3],[6,9]],"newInterval":[2,5]}
Output: [[1,5],[6,9]]
```

**Constraints**
- 0 <= intervals.length <= 10000
- intervals is sorted by start time and starts with non-overlapping closed intervals
- -100000 <= start <= end <= 100000
- -100000 <= new_interval[0] <= new_interval[1] <= 100000

**Follow-up**
Can you finish the insertion in one pass without re-sorting the whole list?

- `intervals` arrives pre-sorted and non-overlapping, so the only disorder in the whole array comes from inserting `newInterval` once.
- Because of that guarantee, you never need a general sort or an O(n^2) overlap check — a single left-to-right scan is enough to find exactly where the new interval lands.

Understand the Goal

- Split the array into three contiguous phases relative to `newInterval`: intervals that end strictly before it starts, intervals that overlap it, and intervals that start strictly after it ends.
- "Overlap" here includes endpoint-touching intervals like `[1,2]` and `[2,3]` — treat `<=`/`>=` (not strict `<`/`>`) as the overlap test, since a merged `[1,3]` is still a single valid interval and keeping `[1,2],[2,3]` separate would be a needlessly fragmented answer.

Choose the Core Pattern

- Phase 1: while the current interval's end is strictly less than the new interval's start, it can't overlap — copy it through unchanged.
- Phase 2: while the current interval's start is <= the new interval's end, they touch or overlap — absorb it by taking the min of starts and max of ends, growing `newInterval` in place rather than emitting anything yet.
- After phase 2 ends (or immediately if it never ran), emit the now-final merged interval exactly once.
- Phase 3: copy every remaining interval through unchanged — by definition none of them can touch the merged interval, since the scan already passed the last one that could.

Build the Algorithm

- Empty `intervals`: phases 1 and 3 run zero times and phase 2 also runs zero times, so the result is just `[newInterval]`.
- `newInterval` fits entirely before the first interval or after the last: it participates in zero merges and is emitted as its own entry in the correct position.
- `newInterval` fully contains one or more existing intervals: the min/max absorption in phase 2 naturally swallows them without special-casing containment separately from partial overlap.