Merge Overlapping Incident Intervals for Downtime
Problem Statement
Compute total downtime from a set of alert intervals that may overlap or be reported by multiple monitors. Overlapping intervals count once.
Background
Given a list of (start, end) outage intervals, merge overlapping/adjacent ones and sum their lengths. Two intervals overlap if one starts at or before the other ends. The total downtime is the sum of merged interval lengths.
Your Task
def total_downtime(intervals):
Return the total covered duration (number).
Input Format
- intervals (list of (start, end) numeric tuples, start <= end).
Output Format
- A number (total downtime).
Sample
print(total_downtime([(0, 10), (5, 15), (20, 25)]))
Output:
20
Example:
print(total_downtime([(0, 10), (5, 15), (20, 25)]))
20
- Sort the input intervals by their start times to process them in chronological order: [(0,10),(5,15),(20,25)].
- Initialize the current merged interval with the first pair, setting the current start to 0 and current end to 10.
- Process the next interval (5,15): since its start (5) is less than or equal to the current end (10), the intervals overlap; update the current end to the maximum of 10 and 15, resulting in a merged interval of [0,15].
- Process the final interval (20,25): since its start (20) is greater than the current end (15), there is no overlap; add the length of the previous merged interval (15−0=15) to the total and start a new current interval [20,25].
- Add the length of the last remaining interval to the total: 15+(25−20)=15+5=20.
- The final output is 20
Constraints:
- Merge intervals that overlap or touch (
next.start <= cur.end). - Sum merged lengths.
- Empty list -> 0.
1. Background Knowledge
This problem is a classic application of the interval merging pattern, frequently encountered in scheduling, resource allocation, and observability monitoring. In an SLO (Service Level Objective) context, multiple monitors may report overlapping downtime windows. To compute accurate total downtime, you must account for the fact that overlapping periods should only be counted once.
The core mathematical concept here is the union of intervals. If you have intervals [a,b] and [c,d], they overlap if and only if a≤d and c≤b. When intervals overlap or are adjacent (where the end of one equals the start of the next), they can be merged into a single continuous interval. The total downtime is simply the sum of the lengths of these merged, non-overlapping intervals.
A key insight is that sorting the intervals by their start time is the most efficient way to process them. Once sorted, you only need to compare each interval with the current "active" merged interval. If the next interval starts before or at the end of the current merged interval, they overlap and can be extended. Otherwise, the current merged interval is finalized, and you start a new one.
2. Algorithm Approach
The standard approach is sort-and-scan:
- Sort the input intervals by their start time.
- Iterate through the sorted intervals, maintaining a "current merged interval" (initialized with the first interval).
- For each subsequent interval:
- If it overlaps with the current merged interval (i.e., its start ≤ current end), update the current end to be the maximum of the two ends.
- If it does not overlap, add the length of the current merged interval to the total downtime, and start a new current merged interval with the next one.
- After the loop, add the length of the final current merged interval to the total.
This is a greedy algorithm because at each step, you make the locally optimal choice (merge if possible) which leads to the globally optimal solution (minimum number of merged intervals).
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.