Merge Overlapping Maintenance Windows | Dataford Interview Questions

Google Cloud infrastructure can contain maintenance windows that overlap across services. Given a list of maintenance windows, merge all overlapping or directly adjacent windows and return the smallest equivalent set of non-overlapping windows.

Formal Specification

Implement merge_maintenance_windows(windows), where windows is a list of two-element lists. Each window [start, end] represents the half-open interval [start, end), with integer timestamps measured in minutes. Return a list of two-element lists sorted by start. If one window begins exactly when another ends, merge them because there is no uncovered minute between them.

The input list may be unsorted. Do not modify the caller's input list unless your implementation explicitly documents that behavior.

Constraints

0 <= len(windows) <= 10^5
Each window has exactly two integer endpoints
0 <= start <= end <= 10^9
The output is sorted by start time
The output contains no overlapping or adjacent windows

Function Signature

def merge_maintenance_windows(windows):

Your question is Merge Overlapping Maintenance Windows. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem