Module 10 · Intervals and Sweep-Line Events

094. Total Covered Length

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the total length covered by the union of half-open numeric intervals [start,end), with start<=end. Overlaps count only once. Empty intervals add zero length, and empty input returns zero. Do not modify the intervals.

Examples

Example 1

covered_length([(1,4),(2,6),(8,10)])
=> 7

The merged lengths are five and two.

Example 2

covered_length([(1,2),(2,3)])
=> 2

Touching ranges can be coalesced for length measurement.

Example 3

covered_length([])
=> 0

The empty union has length zero.

Reveal the worked solution and reasoning

Why this mechanism works

After sorting by start, overlapping or touching intervals can be represented by one active union segment. Only when a real gap begins is the current segment's length final. Summing finalized disjoint lengths avoids double-counting overlap.

State and boundaries

start,end describe the active merged segment. total contains lengths of earlier finalized segments.

Protocol

Sort intervals and handle an empty collection.
Extend the active end while the next start<=end.
On a gap add end-start and start a new segment.
Add the final segment length.

Visualization

[1,4) + [2,6) -> [1,6), length 5
[8,10) adds 2
total covered length 7

Python implementation

def covered_length(intervals):
    ordered = sorted(intervals)
    if not ordered:
        return 0
    start, end = ordered[0]
    total = 0
    for next_start, next_end in ordered[1:]:
        if next_start <= end:
            end = max(end, next_end)
        else:
            total += end - start
            start, end = next_start, next_end
    return total + end - start

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

covered_length([(1,4),(2,6),(8,10)])

L2 covered_length: ordered = sorted(intervals)
intervals=[(1, 4), (2, 6), (8, 10)]; ordered=[(1, 4), (2, 6), (8, 10)]

L5 covered_length: start, end = ordered[0]
intervals=[(1, 4), (2, 6), (8, 10)]; ordered=[(1, 4), (2, 6), (8, 10)]; start=1; end=4

L6 covered_length: total = 0
intervals=[(1, 4), (2, 6), (8, 10)]; ordered=[(1, 4), (2, 6), (8, 10)]; start=1; end=4; total=0

L7 covered_length: for next_start, next_end in ordered[1:]:
intervals=[(1, 4), (2, 6), (8, 10)]; ordered=[(1, 4), (2, 6), (8, 10)]; start=1; end=4; total=0; next_start=2; next_end=6

L9 covered_length: end = max(end, next_end)
intervals=[(1, 4), (2, 6), (8, 10)]; ordered=[(1, 4), (2, 6), (8, 10)]; start=1; end=6; total=0; next_start=2; next_end=6

L7 covered_length: for next_start, next_end in ordered[1:]:
intervals=[(1, 4), (2, 6), (8, 10)]; ordered=[(1, 4), (2, 6), (8, 10)]; start=1; end=6; total=0; next_start=8; next_end=10

L11 covered_length: total += end - start
intervals=[(1, 4), (2, 6), (8, 10)]; ordered=[(1, 4), (2, 6), (8, 10)]; start=1; end=6; total=5; next_start=8; next_end=10

L12 covered_length: start, end = next_start, next_end
intervals=[(1, 4), (2, 6), (8, 10)]; ordered=[(1, 4), (2, 6), (8, 10)]; start=8; end=10; total=5; next_start=8; next_end=10

Result: 7. The merged lengths are five and two.

covered_length([(1,2),(2,3)])

L2 covered_length: ordered = sorted(intervals)
intervals=[(1, 2), (2, 3)]; ordered=[(1, 2), (2, 3)]

L5 covered_length: start, end = ordered[0]
intervals=[(1, 2), (2, 3)]; ordered=[(1, 2), (2, 3)]; start=1; end=2

L6 covered_length: total = 0
intervals=[(1, 2), (2, 3)]; ordered=[(1, 2), (2, 3)]; start=1; end=2; total=0

L7 covered_length: for next_start, next_end in ordered[1:]:
intervals=[(1, 2), (2, 3)]; ordered=[(1, 2), (2, 3)]; start=1; end=2; total=0; next_start=2; next_end=3

L9 covered_length: end = max(end, next_end)
intervals=[(1, 2), (2, 3)]; ordered=[(1, 2), (2, 3)]; start=1; end=3; total=0; next_start=2; next_end=3

Result: 2. Touching ranges can be coalesced for length measurement.

Why the solution is correct

Extending an overlapping segment preserves its union while counting no length twice. A gap proves later starts cannot extend the old segment, so its length can be committed. Finalized segments are disjoint and together cover exactly the input union.

Time and space

O(n log n) time and O(n) sorting space; O(1) scan state.

Common mistakes

Summing input lengths double-counts overlap. Forgetting the final commit loses the last union segment.

Reasoning card

State: start,end describe the active merged segment. total contains lengths of earlier finalized segments.

Invariant: Active segment is the union since the latest gap.

Decision to rehearse: Merge an active segment and commit only when a true gap appears.

Finish: Add the final segment length

Transfer exercise

Return the covered length within a query interval by intersecting with the already merged union.