Sweep-line thinking

Greedy choices and intervals Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
spans = [[1, 4], [2, 6], [8, 9]]
starts = [(s, 1) for s, _ in spans]
events = sorted(starts + [(e, -1) for _, e in spans])
live, last, covered = 0, 0, 0
for t, d in events:
    if live:
        covered += t - last
    live += d
    last = t
print(covered)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 6

Right: [1, 6) covers 5 and [8, 9) covers 1.

The running count decides whether time between events is covered, so overlaps are never double-counted.

Why not the others?
  • B 8. Overlaps are counted once, not twice.
  • C 4. The first two spans together cover 1 to 6.

30-second answer

A sweep line turns intervals into events (start and end points), sorts them, and walks through them in order while maintaining a running state: a count, a set of active items or a running total. It solves peak overlap, total covered length, free gaps and 'which items are active at time t' questions in O(n log n).

Practise saying it · 45 s. No recording, just a timer

Explain a sweep line.

Say your answer out loud, then check which of these points you covered:

  • Events
  • Sorted walk
  • Running state

Deep dive

Break ties carefully: half-open intervals process ends before starts.

With integer times in a small range, a difference array replaces the sort.

The active set can be a heap when you need its minimum or maximum.

Common mistakes

  • Wrong tie order, which changes the answer on touching intervals.
  • Processing intervals instead of events, which misses mid-interval changes.

Senior take & follow-ups

Describe the state you keep during the sweep; that is the design.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you compute the total length covered?

    Show hint

    Sweep events with a count; add the distance since the last event whenever the count is above zero.

  2. What is a difference array?

    Show hint

    Add +1 at start and -1 at end in an array over time, then take prefix sums.

What each operation costs: Merge Sort · Quick Sort

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.