Algorithms / Sweep Line Lite
Least You Need to Know: Sweep-Line Lite, Event Ordering, and Active Counts
Sweep-line problems turn geometry or scheduling into a sorted stream of events. The main invariant is an active count or active set that changes only at endpoints, so careful event ordering is often the difference between a correct solution and an off-by-one bug.
The least you need to know
- A sweep line processes sorted event coordinates from left to right.
- Many counting problems need only an active count instead of the full active set.
- The maximum active count gives peak overlap in meeting-room and coverage problems.
- Tie-breaking at equal coordinates depends on whether endpoints are closed or half-open.
- Sweep-line reasoning often replaces `O(n^2)` pair comparisons with sorting plus a linear scan.
Key notation
event = (x, type)
something starts or ends at coordinate `x`
active
number of currently open intervals or objects
max_active
largest overlap seen during the sweep
Tiny worked example
- For meeting intervals treated as `[start, end)`, process end events before start events at the same time.
- That way, one meeting ending at `10` frees a room before another starting at `10` needs it.
- The active count then matches the true room requirement.
Common mistakes
- Equal-coordinate event order is not cosmetic; it encodes the interval semantics.
- You often do not need the full geometry, only how the active count changes at events.
- A sweep line is still about the original model, so the event encoding must match the problem statement.
How to recognize this kind of problem
- The prompt asks for maximum simultaneous activity, union size, or offline answers tied to sorted coordinates.
- Brute-force comparison of all pairs feels wasteful but sorted endpoints seem meaningful.
- Correctness hinges on what happens when starts and ends share the same coordinate.