You have a list of closed intervals, sorted by start and pairwise non-overlapping, and one new interval. Insert the new interval and merge wherever it overlaps, so the result is again sorted and non-overlapping. Return the resulting list.
Examples
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: [4,8] bridges [3,5], [6,7] and [8,10] into one.
Example 3:
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Example 4:
Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]
Explanation: already covered; nothing changes.
Constraints
0 <= intervals.length <= 10^4
intervals is sorted by start; intervals[i] and newInterval are [start, end] with 0 <= start <= end <= 10^5
Prerequisites
Sorting as a setup move — most interval problems are one sort away from a single sweep, and choosing whether to sort by START or by END is the decision that matters.
How to think about it
1. Three Phases in One Pass Optimal
Intuition
The input is already sorted and disjoint, which is the gift: everything ending before the new interval starts is untouched, everything overlapping it gets absorbed into one widened interval, and everything after is untouched again. Three phases, one pass, no sorting.
Algorithm
1. Copy intervals that end before the new one starts. 2. While the next interval starts at or before the new one's end, widen the new one — minimum of starts, maximum of ends. 3. Place the widened interval, then copy the rest.