Standard Bar Greedy Approach · Medium O(n) · O(n)
A datacenter keeps an ordered list of non-overlapping maintenance windows. Ops files one new window that may overlap several existing ones. The calendar tool walks the sorted list: it copies every window that ends before the new one starts, absorbs every window it collides with by stretching the new one, and finally slots the (possibly enlarged) window before whatever remains.
Input: A sorted non-overlapping list of intervals and a newInterval [start, end].
Output: Return the merged, still-sorted, non-overlapping interval list.
0 <= intervals.length <= 10^4-10^4 <= start <= end <= 10^4intervals is sorted by start and non-overlappingInput: {"intervals":[[1,2],[3,5],[6,7],[8,10],[12,16]],"newInterval":[4,8]}
Output: [[1,2],[3,10],[12,16]]
[4,8] swallows [3,5], [6,7] and [8,10] into one stretched window.
Input: {"intervals":[[1,3],[6,9]],"newInterval":[2,5]}
Output: [[1,5],[6,9]]
[2,5] merges with [1,3] and stays clear of [6,9].