DiffPush Tier Arrays · Hard O(n log n) · O(n) for the merged output
A datacenter scheduler collected maintenance bookings as start and end times from several teams, so the list is unsorted and the windows may touch or overlap. Before publishing downtime, overlapping windows have to be collapsed into the smallest set of disjoint windows that still covers every booked minute.
Input: An array intervals where intervals[i] = [start_i, end_i] with start_i <= end_i.
Output: A list of non-overlapping intervals with start <= end, sorted by start, covering exactly the minutes of the input intervals.
1 <= n <= 10^40 <= start_i <= end_i <= 10^4Input: {"intervals":[[1,3],[2,6],[8,10],[15,18]]}
Output: [[1,6],[8,10],[15,18]]
The first two windows overlap and collapse into [1,6], while the later windows stay separate.
Input: {"intervals":[[1,4],[4,5]]}
Output: [[1,5]]
Windows that merely touch at minute 4 are treated as connected and fuse into a single window.