Skip to content
Hari KharelStudy

Sweep line

intermediateCommon atGoogleMetaAmazonBloombergRead firstIntervalsSorting and comparatorsPractise in the Sandbox →

Replace each interval with two events: +1 at its start and −1 at its end. Sort the events by coordinate and walk them once, keeping a running active count (or an active set). The answer to “how many at once”, “how much is covered” or “what’s open at x” falls out in O(n log n). At equal coordinates, the tie-break order encodes whether endpoints are included.

The idea in plain words

Section titled “The idea in plain words”

Imagine a vertical line sliding left to right across a timeline. Nothing interesting happens between endpoints: the set of intervals under the line only changes at a start or an end. So instead of checking every moment, you jump from event to event.

At each event you update a small state:

  • a counter (active += 1 on start, −= 1 on end) for “how many overlap here”,
  • a running total of covered length since the previous event,
  • or a richer structure (a heap, a sorted set) when you need to know which intervals are active, not just how many.

The subtle part is the order of events at the same x. If one interval ends at 10 and another starts at 10, do they overlap? With half-open ranges [s, e), no: process the end first. With closed ranges [s, e], yes: process the start first. Getting this wrong is the most common sweep bug, and it only shows up on touching inputs.

See it

Section titled “See it”

The default input has intervals that touch at 4 and at 9. Step through with “end before start”, then flip the tie rule and step again. The peak changes.

Sweep the events, count what's open
step through
[1,4][2,5][4,7][6,9][9,11][3,4]active01234567891011
1+
2+
3+
4−
4−
4+
5−
6+
7−
9−
9+
11−
events in sweep order: x then + (start) or − (end)
x–
active0
peak0
covered0
event being processedopen (active) intervalalready closed
Each interval becomes two events: +1 at its start, −1 at its end. Sorted by x, ends before starts on ties.
1 / 14

When to reach for it

Section titled “When to reach for it”
The problem says… Why a sweep fits
“maximum number at the same time”, “peak concurrency”, “busiest moment” The running count is the concurrency; take its max.
“total time covered”, “union length”, “time when at least one is active” Add x − prev_x whenever the count is positive.
“for each query point, how many intervals contain it” Make queries events too; read the count when you reach them.
“skyline”, “outline of overlapping rectangles” Events at building edges; an active set (max-heap) gives the height.
Simulations over time with arrivals and departures Events sorted by time, with a priority queue if new events are created on the fly. See event-driven simulation.

How it works

Section titled “How it works”
  1. Make events. Each interval produces (start, open) and (end, close). Extra things to report on (query points) become events too.
  2. Choose the tie-break. Encode it in the sort key: e.g. (x, kind) where kind 0 = close for half-open, or 0 = open for closed ranges. Write it down; don’t rely on the language’s tuple order by accident.
  3. Sort the events: O(n log n).
  4. Sweep. For each event, first account for the stretch since the last event (it had the old state), then apply the event.

Union length of half-open ranges. Note that (x, −1) sorts before (x, +1) with plain tuple ordering, which is exactly “end before start”.

covered_length.py
Interval = tuple[int, int]




def covered_length(intervals: list[Interval]) -> int:
    """Total length of the union of half-open [s, e) ranges (Klee's measure in 1-D)."""
    events: list[tuple[int, int]] = []
    for s, e in intervals:
        events.append((s, +1))                  # 1. one event per endpoint
        events.append((e, -1))
    events.sort()                               # 2. by x; on ties -1 sorts before +1 (end first)
    active = covered = 0
    prev_x = 0
    for x, delta in events:
        if active > 0:                          # 3. the gap since the last event was covered
            covered += x - prev_x
        active += delta                         # 4. then apply this event
        prev_x = x
    return covered




if __name__ == "__main__":
    assert covered_length([(1, 4), (2, 5), (7, 9)]) == 6   # [1,5) + [7,9)
    assert covered_length([(1, 3), (3, 6)]) == 5           # touching: no double count
    assert covered_length([(0, 10), (2, 3)]) == 10         # containment
    assert covered_length([]) == 0
    print("ok")

Three event kinds with an explicit tie order: for closed intervals, a query at x must see intervals that start at x and those that end at x, so the order is open, then query, then close.

coverage_at.py
Interval = tuple[int, int]


START, QUERY, END = 0, 1, 2   # tie order at the same x: open, then ask, then close




def coverage_at(intervals: list[Interval], points: list[int]) -> list[int]:
    """For each point, how many closed [s, e] intervals contain it. Offline sweep."""
    events: list[tuple[int, int, int]] = []
    for s, e in intervals:
        events.append((s, START, 0))            # 1. intervals become open/close events
        events.append((e, END, 0))
    for i, x in enumerate(points):
        events.append((x, QUERY, i))            # 2. queries are events too
    events.sort()                               # 3. closed ends: a query at x sees [.., x] and [x, ..]
    answer = [0] * len(points)
    active = 0
    for _, kind, i in events:
        if kind == START:
            active += 1
        elif kind == END:
            active -= 1
        else:
            answer[i] = active                  # 4. read the running count
    return answer




if __name__ == "__main__":
    ivs = [(1, 6), (3, 7), (9, 12), (4, 13)]
    assert coverage_at(ivs, [2, 3, 7, 11, 14]) == [1, 2, 2, 2, 0]
    assert coverage_at(ivs, [6]) == [3]         # 6 is the closing end of [1, 6]
    assert coverage_at([], [1]) == [0]
    print("ok")

What it costs

Section titled “What it costs”
Approach Time Space
Check every point of time against every interval O(n · range) O(1)
Compare every pair of intervals O(n²) O(1)
Sweep with a counter O(n log n) (the sort) + O(n) O(n) events
Sweep with an active set (heap / sorted set) O(n log n) O(n)
Difference array over small integer coordinates O(n + M) O(M)
Online: events arrive already in time order O(1) per event (counter), O(log n) (active set) O(active)

The sweep turns a 2-D question (intervals × time) into a 1-D walk. The sort is the floor: you can’t process events in order without ordering them, unless they’re small integers.

How fast does work grow?
drag n
2565127681.0kinput size n →
n = 16
O(n log n): 64 opsO(n²): 256 ops

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Count only (peak overlap, coverage, “at least k active for how long”): an integer counter.
  • Which intervals are active: an active set. Use a min-heap of end times when you only need the earliest finisher, or a sorted set (SortedSet<T> in C#, sortedcontainers or a heap with lazy deletion in Python) when you need to remove arbitrary ones.
  • Assigning resources (which machine or server gets each job): a heap of busy-until times, often plus a heap of free resources. See heaps.
  • Weighted events: each interval adds its weight (bandwidth, load) instead of 1.
  • 2-D sweeps: sweep x, keep a structure over y (a segment tree for rectangle union area, a balanced BST for segment intersection).
  • Offline queries: sort queries with the events, answer each when the line reaches it (the second sample above).

Pitfalls

Section titled “Pitfalls”
  • Wrong tie order. End-before-start for half-open, start-before-end for closed. Test with two intervals that touch.
  • Updating before measuring. In coverage sums, add x − prev_x using the count before applying the current event.
  • Sorting tuples in JavaScript. events.sort() compares as strings: 10 sorts before 9. Always (a, b) => a[0] - b[0] || a[1] - b[1].
  • Relying on accidental tuple order. In Python, (x, -1) < (x, 1) happens to mean end-first. If you later switch to strings like "start"/"end", alphabetical order flips the meaning. Use explicit rank constants.
  • Counting the peak at the wrong moment. Record the max right after applying a +1, not after a −1.
  • Zero-length intervals. [5, 5) is empty; [5, 5] is a point. Decide whether they produce events at all.

In the interview

Section titled “In the interview”
  • Ask: closed or half-open endpoints? Can intervals be zero-length? Is the input sorted? Are coordinates small integers (difference array) or arbitrary?
  • Say the tie rule out loud: “At equal times I process ends first, because a meeting ending at 10 frees its slot for one starting at 10.” Interviewers listen for this.
  • State the invariant: “Between events, active equals the number of intervals covering every point in that stretch.”
  • Follow-ups to expect: return when the peak happens, return which intervals are active at the peak, handle a stream of events, weights instead of counts, and the 2-D version (rectangles).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
Half-open intervals [1, 5), [5, 8), [2, 5). With events sorted start-before-end at equal x, what peak does the sweep report?
Check yourself
pick one
Coordinates are integers between 0 and 1,000 and there are 10 million intervals. What's the cheapest way to get the peak overlap?
Check yourself
pick one
You sum covered length with `covered += x - prev_x` inside the loop. Should that line run before or after `active += delta`?

Practice on your own

Section titled “Practice on your own”

Classic exercises (not gym questions):

  • The skyline problem: given buildings (left, right, height), output the outline’s key points.
  • Given people’s birth and death years, find the year with the most people alive (decide: is someone alive in their death year?).
  • Area of the union of axis-aligned rectangles (sweep x, segment tree over y).
  • Given flights as (takeoff, landing), the maximum number of planes in the air.
  • For each of q query times, how many intervals contain it, in O((n + q) log(n + q)).

Go deeper

Section titled “Go deeper”
Section titled “Related”
IntervalsOverlap tests, merging and the endpoint convention.
Prefix sums and difference arraysThe sweep without sorting, for small integer coordinates.
HeapsTrack which intervals are active, earliest end on top.
Event-driven simulationThe same idea when events create new events.