Consolidate Maintenance Windows
Efficiently managing system maintenance is crucial for large-scale platforms like Meta. When multiple teams schedule maintenance windows, their interdependencies often require consolidation to minimize disruption and ensure critical systems are handled cohesively. This problem focuses on intelligently merging maintenance schedules based on their overlap.
Given a list of maintenance windows, each represented as an interval [start, end], and a minimum overlap duration k, your task is to consolidate all maintenance windows that overlap by at least k units of time. If a group of windows can be transitively merged (e.g., A overlaps B by k, and B overlaps C by k), they should all be consolidated into a single, larger window.
Your solution should return a new list of non-overlapping, consolidated maintenance windows, sorted by their start times.
windows: An array of [start, end] integer pairs, where start is the beginning time and end is the ending time of a maintenance window. start < end for all windows.k: An integer representing the minimum required overlap duration for two windows to be considered for consolidation.[start, end] integer pairs representing the consolidated maintenance windows, sorted by their start times.windows is empty, return an empty array [].windows contains only one interval, it should be returned as is.[s1, e1] and [s2, e2] is max(0, min(e1, e2) - max(s1, s2)). Note that if min(e1, e2) - max(s1, s2) is negative, there is no overlap, and thus the duration is 0.k Value: k will always be a non-negative integer.Examples
Example 1
Input:
windows = [[1,5],[4,8],[10,12]], k = 1
Output:
[[1,8],[10,12]]
Note:
Intervals [1,5] and [4,8] overlap by min(5,8) - max(1,4) = 5 - 4 = 1. Since 1 >= k (which is 1), they are merged into [1,8]. The interval [10,12] does not overlap with [1,8] by at least k, so it remains separate.
Example 2
Input:
windows = [[1,5],[4,8],[10,12]], k = 2
Output:
[[1,5],[4,8],[10,12]]
Note:
Intervals [1,5] and [4,8] overlap by 1. Since 1 < k (which is 2), they are not merged. All intervals remain separate.
Example 3
Input:
windows = [[1,10],[3,7],[6,12]], k = 2
Output:
[[1,12]]
Note:
Initially, sort to [[1,10],[3,7],[6,12]].
Example 4
Input:
windows = [], k = 5
Output:
[]
Note:
Empty input results in an empty output.
Constraints
0 <= windows.length <= 10^50 <= start < end <= 10^9 for all [start, end] in windows0 <= k <= 10^9windows are not necessarily sorted.k overlap threshold?Loading editor...