Write insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]].
intervals is sorted by start and its intervals are pairwise disjoint (they don't even touch). Insert new_interval = [start, end] and merge wherever needed. Return a list that is still sorted and disjoint. As usual, touching intervals merge: [1, 3] and [3, 5] become [1, 5].
Example: intervals = [[1, 2], [4, 5], [7, 9], [12, 15]], new_interval = [5, 8] gives [[1, 2], [4, 9], [12, 15]].
intervals = [], new_interval = [2, 6] gives [[2, 6]].
Constraints: up to 10^5 intervals, 0 <= start <= end <= 10^9.
The input is already sorted, so aim for a single O(n) pass rather than re-sorting or merging from scratch.
Show hint
the existing intervals fall into three runs: those entirely before the new one, those that overlap it, and those entirely after.