Merge Overlapping Incident Intervals for Downtime

mediumPROObservability & SLOsSystems & InfrastructureML Systems & Infrastructure 1

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:

Example

Input

print(total_downtime([(0, 10), (5, 15), (20, 25)]))

Output

Reasoning

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.

Learn this in

Patterns & MiscellaneousDSA Study Plan Monitoring & ObservabilitySystems & Networking

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium

Concept primerPREVIEW

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 \le d$ and $c \le 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 $\le$ 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

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results