Frontend School

Consolidate Maintenance Windows

DSA
medium

Consolidate Maintenance Windows

Medium
Intervals
Sorting

Overview

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.

What you need to do / Task

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.

Input & output

  • 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.
  • Returns: An array of [start, end] integer pairs representing the consolidated maintenance windows, sorted by their start times.

Clarifications

  • Empty Input: If windows is empty, return an empty array [].
  • Single Interval: If windows contains only one interval, it should be returned as is.
  • Overlap Definition: The overlap duration between two intervals [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

1

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.

2

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.

3

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]].

  • [1,10] and [3,7] overlap by min(10,7)-max(1,3) = 7-3 = 4. Since 4 >= k (2), they merge into [1,10].
  • The current merged [1,10] and [6,12] overlap by min(10,12)-max(1,6) = 10-6 = 4. Since 4 >= k (2), they merge into [1,12]. All intervals consolidate into one.
4

Example 4

Input:

windows = [], k = 5

Output:

[]

Note:

Empty input results in an empty output.

Constraints

Constraints & assumptions

  • 0 <= windows.length <= 10^5
  • 0 <= start < end <= 10^9 for all [start, end] in windows
  • 0 <= k <= 10^9
  • The input windows are not necessarily sorted.

What interviewers evaluate

  • Algorithm Correctness: Does the solution correctly identify and merge intervals based on the k overlap threshold?
  • Time Complexity: Is the solution efficient, ideally achieving O(N log N) time complexity for N intervals?
  • Space Complexity: Does the solution use space optimally, ideally O(N) for the result or O(1) if in-place modification is considered for sorted input?
  • Code Quality: Is the code clean, readable, and well-structured, demonstrating good software engineering practices?

Loading editor...