Slot In the Downtime

medium

A server's maintenance calendar is a list of downtime windows — [start, end] pairs already sorted by start and non-overlapping. Ops wants to schedule one more window, new_window, and keep the calendar clean.

Insert new_window, merging it with any windows it overlaps or touches, and return the resulting sorted, non-overlapping list. Don't assume you may mutate the input order guarantees away — the output must hold the same invariants.

Example 1

in windows = [[1, 3], [6, 9]], new_window = [2, 5]

out [[1, 5], [6, 9]]

[2, 5] overlaps [1, 3]; they fuse into [1, 5].

Example 2

in windows = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new_window = [4, 8]

out [[1, 2], [3, 10], [12, 16]]

[4, 8] chains [3, 5], [6, 7], and [8, 10] into one block.

Constraints

· 0 <= len(windows) <= 2000
· windows is sorted by start and non-overlapping
· 0 <= start <= end <= 10^6