The "Maintenance Window" Problem
SREs schedule maintenance windows, on-call rotations, and deployment freezes. A common operational question is: "Given a list of overlapping maintenance windows, what is the total downtime?" To answer this, you need to merge overlapping intervals into a single, non-overlapping list.
For example:
- Window A: [1:00, 3:00]
- Window B: [2:00, 5:00]
- Window C: [7:00, 9:00]
Merged result: [[1:00, 5:00], [7:00, 9:00]] — total downtime is 6 hours, not 7.
The Algorithm: Sort, Then Scan
The key insight is that overlapping intervals are only adjacent to each other after sorting. Without sorting, you would need to compare every interval against every other — O(N²). Sorting first reduces this to a single linear scan.
def merge_intervals(intervals):
if not intervals:
return []
# Step 1: Sort by start time — O(N log N)
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]] # Start with the first interval
# Step 2: Linear scan — O(N)
for current_start, current_end in intervals[1:]:
last_start, last_end = merged[-1]
if current_start <= last_end:
# Overlap detected — extend the last interval if needed
merged[-1] = (last_start, max(last_end, current_end))
else:
# No overlap — add as a new interval
merged.append((current_start, current_end))
return merged
# Example
windows = [(1, 3), (2, 5), (7, 9), (8, 10)]
print(merge_intervals(windows))
# [(1, 5), (7, 10)]
Why max(last_end, current_end)? Consider a window fully contained within another: [(1, 10), (3, 5)]. After sorting, when we process (3, 5), the last merged interval is (1, 10). The current end (5) is less than the last end (10). Taking the max correctly keeps (1, 10) intact.
Complexity: O(N log N) for sorting, O(N) for the scan. Total: O(N log N).
SRE Applications Beyond Scheduling
Interval merging appears in more places than scheduling:
- Alert deduplication: Merge overlapping alert windows to count distinct incidents.
- Log correlation: Find time ranges where multiple services were simultaneously degraded.
- Capacity planning: Merge overlapping high-traffic windows to calculate peak load duration.