Sweep Line

Objectives and sequence#

• Turn interval endpoints into ordered events and define the active-state meaning.
• Group all changes at an equal coordinate before evaluating a post-coordinate state.
• Use half-open [start,end) intervals to make touching endpoints unambiguous.
• Distinguish peak overlap from total union length instead of treating them as the same query.

Recognition boundaries#

From baseline to method#

Simple baseline: For peak overlap, compare each interval with every other interval or sample every coordinate. For union length, repeatedly test coverage at individual positions. Pair comparison is O(n²), and coordinate sampling is invalid for large or continuous domains.

1. Represent each nonempty half-open interval [start,end) with +1 at start and -1 at end.
2. Sort event coordinates and combine all deltas at the same coordinate so input order cannot decide ties.
3. Before applying the delta at x, add x-previousX to union length exactly when the old active count is positive.
4. Apply the grouped delta, then update peak from the new active count. Half-open intervals ending at x no longer overlap intervals beginning at x.
5. Peak overlap and union length share events but answer different questions: one maximizes state, the other integrates positive coverage across coordinate gaps.

Worked example#

For half-open intervals, return both peak overlap and total covered length.

Input

intervals = [[1,4), [2,6), [6,8), [9,11)]

Contract

Endpoints are integers, start ≤ end, zero-length intervals contribute nothing, and intervals use [start,end) semantics.

Expected

peakOverlap = 2, unionLength = 9

Trace summary: For each sorted coordinate, first add the preceding gap when active is positive, then apply that coordinate's grouped start/end delta and update the peak.

Pseudocode and tested references#

The pseudocode treats coordinates and the delta map abstractly. The tested references use integer/long coordinates, group equal coordinates in an ordered map, and return a named pair rather than relying on endpoint sort order.

summarizeIntervals(intervals):
  delta = empty map from coordinate to integer
  for [start, end) in intervals:
    if start == end: continue
    delta[start] += 1
    delta[end] -= 1
  active = 0; peak = 0; unionLength = 0; previous = none
  for x in sorted(delta.keys):
    if previous exists and active > 0: unionLength += x - previous
    active += delta[x]
    peak = max(peak, active)
    previous = x
  return (peak, unionLength)

def summarize_intervals(intervals):
    delta = {}
    for start, end in intervals:
        if start > end:
            raise ValueError("expected start <= end")
        if start == end:
            continue
        delta[start] = delta.get(start, 0) + 1
        delta[end] = delta.get(end, 0) - 1

    active = peak = union_length = 0
    previous = None
    for coordinate in sorted(delta):
        if previous is not None and active > 0:
            union_length += coordinate - previous
        active += delta[coordinate]
        peak = max(peak, active)
        previous = coordinate
    return {"peak_overlap": peak, "union_length": union_length}

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public final class SweepLineReference {
    public record Interval(long start, long end) {}
    public record Summary(int peakOverlap, long unionLength) {}

    public static Summary summarizeIntervals(List<Interval> intervals) {
        Map<Long, Integer> delta = new TreeMap<>();
        for (Interval interval : intervals) {
            if (interval.start() > interval.end()) {
                throw new IllegalArgumentException("expected start <= end");
            }
            if (interval.start() == interval.end()) continue;
            delta.merge(interval.start(), 1, Integer::sum);
            delta.merge(interval.end(), -1, Integer::sum);
        }

        int active = 0;
        int peak = 0;
        long unionLength = 0;
        Long previous = null;
        for (Map.Entry<Long, Integer> event : delta.entrySet()) {
            long coordinate = event.getKey();
            if (previous != null && active > 0) unionLength += coordinate - previous;
            active += event.getValue();
            peak = Math.max(peak, active);
            previous = coordinate;
        }
        return new Summary(peak, unionLength);
    }
}

Time

O(n log n) to build and order at most 2n event coordinates; the sweep itself is O(n).

Space

O(n) for grouped events.

Assumptions

Intervals are static, half-open, and use integer coordinates; accumulated union length fits Python integer or Java long in the references.

Failure modes and edges#

Edge cases

• Empty input returns peak 0 and union length 0.
• A zero-length [x,x) interval contributes neither activity nor length.
• Touching [a,b) and [b,c) intervals have continuous union but do not overlap each other.
• Duplicate intervals increase peak multiplicity but not union length.
• Nested intervals change peak while leaving the outer union boundary unchanged.
• Negative coordinates work because only sorted order and differences matter.

Wrong approaches

Three-stage hint ladder#

Narrated reasoning

I will state [start,end) first so equal endpoints have one precise meaning. Both answers can share event deltas, but I must update them at different moments. The current active count covers the gap leading up to x, so I add that gap before changing active. I combine every delta at x before measuring the new active count, preventing input order from manufacturing a tie overlap. I will test touching, duplicate, nested, empty, and zero-length intervals.

Reasoning checkpoints#

Guided exercises

• Given room reservations under [start,end), return only the peak number of simultaneous rooms required.
  Checkpoint: Use the same grouped deltas and update peak after applying each coordinate's net delta; union-length accumulation is unnecessary.
• Given painted integer segments, return only their total union length.
  Checkpoint: Add each coordinate gap when active>0; a peak variable is unnecessary because it answers a different query.

Practice and transfer#

Unseen variant: Return every maximal half-open segment on which the active count is at least two, merging adjacent qualifying gaps.

Checkpoint: The pre-event active state labels [previousX,x); append or extend that gap when active≥2, then apply the grouped delta at x.

Practice handoffs

• Practice capacity eventsUse ordered deltas to enforce a capacity invariant.
• Compare interval mergingChoose a direct sorted scan when the output is merged intervals rather than event-state aggregates.

Follow-up constraints

• How would closed intervals change the equal-coordinate event contract?
• Return the first coordinate at which capacity is exceeded without computing union length.
• Explain when coordinate compression plus a difference array is preferable to an ordered map.

Sources and review#

This original Engineering Foundry lesson received Codex self-review on 2026-09-05; independent human editorial review is not claimed.

• Length of the union of segments (opens in a new tab) - Sorted endpoint sweeping for covered length; the combined grouped-delta contract is independently authored for this lesson.
• MIT 6.006 Introduction to Algorithms lecture notes (opens in a new tab) - Academic cross-check for sorting and algorithmic complexity, not an interview-frequency claim.