Skip to content
Tutorials Center
My learning

Topics

Lesson 205 of 225 ยท Advanced Topics

Sweep Line Algorithms

Learn the sweep line technique: turn intervals and rectangles into sorted events, then scan once to count overlaps, find busy times and compute union area.

Many geometry and scheduling problems look hard because everything happens "at once": hundreds of meetings overlap, rectangles pile on top of each other, segments cross. The sweep line technique tames this by adding time (or a coordinate) as an ordering. Imagine a vertical line that slides from left to right across the plane. It stops only at interesting places, called events, and at each stop you update a small amount of state. Between events nothing changes, so you never need to look there.

The recipe is always the same: (1) turn the input into events, (2) sort the events, (3) process them in order while maintaining a data structure that describes "what the line is touching right now". This lesson applies it to intervals and then to rectangles. It builds on sorting, interval scheduling and heaps.

Events: start and end

An interval [start, end) becomes two events: a +1 at start and a -1 at end. Sort them by position and keep a running total, and the total tells you how many intervals cover each point.

flowchart LR
    A["Intervals"] --> B["Make events<br/>(pos, +1) and (pos, -1)"]
    B --> C["Sort by position"]
    C --> D["Scan once,<br/>update state"]
    D --> E["Answer"]

The sweep line pipeline: build events, sort, scan.

A detail that matters: when an end and a start happen at the same position, which comes first? For half-open intervals [start, end) an interval that ends at 5 does not overlap one that starts at 5, so the -1 must be processed before the +1. Sorting tuples (position, delta) does this for free, because -1 < +1.

Python Maximum number of overlapping meetings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The scan costs O(n) after sorting, so the whole algorithm is O(n log n) time and O(n) space. This is exactly the answer to the classic "minimum number of meeting rooms" question: the maximum overlap is the number of rooms you need.

Recording where the busy periods are

Often you want the actual stretches of time, not just a number. Walk the sorted events and note when the count rises above zero and when it returns to zero. That merges overlapping intervals without the "sort by start and compare with the last one" trick, and the same loop also handles other thresholds, such as "when are at least two people online?".

Python Busy periods and a threshold of two

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the loop only compares the count before and after each event. This "crossing a threshold" idea is the core of many sweep solutions.

Sweeping with a heap

Sometimes the state you maintain is richer than a count. The famous skyline problem gives buildings (left, right, height) and asks for the outline. As the line moves, you need the tallest building currently active. A max-heap holds the active heights; buildings that have ended are removed lazily when they reach the top.

flowchart TD
    S["Sorted x positions"] --> P["At each x: push buildings that start here"]
    P --> Q["Pop heap top while its building has ended"]
    Q --> R["Top of heap = current height"]
    R --> T{"Height changed?"}
    T -- yes --> U["Emit key point (x, height)"]
    T -- no --> V["Continue"]

Lazy deletion keeps the heap simple: stale entries are discarded only when they surface.

Python The skyline of overlapping buildings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each building is pushed once and popped at most once, so the time is O(n log n).

Union area of rectangles

Now a two-dimensional problem: what is the total area covered by a set of axis-aligned rectangles that may overlap? Sweep a vertical line across x. Each rectangle contributes an "open" event at its left edge and a "close" event at its right edge. Between two consecutive event x values the covered part of the line has a constant length, so the area of that strip is covered_length * (x_next - x).

The state is the set of y-intervals currently open. A simple way to track the covered length is to keep, for each elementary y-segment (between consecutive distinct y coordinates), a counter of how many open rectangles cover it. A segment counts as covered when its counter is above zero. This version recomputes the covered length per event in O(n), giving O(n^2) overall, which is fine for a few thousand rectangles; a segment tree brings it down to O(n log n).

flowchart LR
    A["x = 1<br/>open R1"] --> B["strip 1..2<br/>covered length 4"]
    B --> C["x = 2<br/>open R2"]
    C --> D["strip 2..3<br/>covered length 5"]
    D --> E["x = 3<br/>close R1"]

Between events the covered length is constant, so each strip is a simple rectangle.

Python Area of the union of rectangles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counters rather than a plain "on/off" flag are important: two rectangles can overlap in y, and closing one must not uncover a segment the other still covers.

When to reach for a sweep line

Look for these signs: the input is a set of intervals, segments or rectangles; the answer depends on what overlaps at each position; or a brute-force solution compares every pair. Typical problems include meeting rooms, the skyline, union area and perimeter, counting segment intersections, finding the closest pair of points and detecting whether any two segments cross. The only part that changes from problem to problem is the structure you keep while sweeping: a counter, a heap, a sorted set, or a segment tree.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a sweep line over half-open intervals [start, end), what should happen first at a position where one interval ends and another starts?

    An interval that ends at 5 does not overlap one that starts at 5, so the -1 must be applied before the +1, otherwise the count is one too high.
  2. 2. What is the time complexity of finding the maximum overlap of n intervals with a sweep line?

    Sorting the 2n events costs O(n log n); the scan afterwards is linear.
  3. 3. Why does the skyline algorithm use a heap?

    The outline follows the maximum height among buildings the line currently touches, which a max-heap provides in O(1) with O(log n) updates.
  4. 4. In the union-area sweep, why do we use counters per y-segment instead of booleans?

    A segment stays covered until the last rectangle covering it closes, so we need to know how many cover it.

Summary

  • A sweep line turns a geometric or scheduling problem into a sorted list of events and one scan.
  • Sort events by position; at ties, process ends before starts for half-open intervals.
  • A running counter answers overlap questions; a heap answers "what is the maximum right now" (skyline); a counter array or segment tree answers coverage questions (union area).
  • The cost is dominated by sorting: usually O(n log n).

Next: Suffix Automaton