Line Sweep - rFronteddu/general_wiki GitHub Wiki

Line Sweep

Imagine a vertical or horizontal line sweeping across a plane, processing events in sorted order.

It is heavily used in:

  • Interval problems, Computational geometry, Calendar/booking problems, Overlap detection, Skyline problems,

Core Idea

  • Convert objects into events -> Sort events -> Process them in order -> Maintain some dynamic structure while sweeping
  • You are essentially simulating time (or x-axis movement).

Classic Example — Interval Overlaps

Suppose we have intervals: [1,5][2,6][7,9]

Step 1: Convert to events, each interval becomes:

  • (start, +1)
  • (end, -1)

So we get:

  • (1, +1), (5, -1), (2, +1), (6, -1), (7, +1), (9, -1)

Step 2: Sort by time

  • (1, +1), (2, +1), (5, -1), (6, -1), (7, +1), (9, -1)

Step 3: Sweep

Keep a running counter:

Time Change Active
1 +1 1
2 +1 2
5 -1 1
6 -1 0
7 +1 1
9 -1 0

This instantly tells you:

  • Maximum overlap = 2
  • When everything is free (Active = 0)

Because many problems reduce to:

  • “What is happening between sorted boundary events?”
  • Instead of checking every pair (O(n²)), you sort once (O(n log n)) and sweep once (O(n)).

Problems: