The core idea
A sweep line imagines a vertical line moving across the number line from left to right. Instead of reasoning about whole intervals at once, you break each interval into two events: a start event and an end event. Sort all events by position and process them as the line reaches each one.
Events and a counter
- A start event means an interval has opened, so increment an active counter.
- An end event means an interval has closed, so decrement the counter.
The counter tells you how many intervals are active at the current position. Its peak value is the maximum overlap, a number many problems ask for directly.
Tie breaking
When a start and an end land on the same coordinate, the order matters. If touching intervals should count as overlapping, process the start before the end. If touching is allowed and should not count, process the end first. This single choice resolves most boundary bugs.
Why it generalizes
The pattern is the same for counting overlaps, finding free slots, or testing coverage: emit events, sort once, sweep while maintaining a small amount of state. Many geometry and scheduling problems reduce to choosing what that state should be.
Key idea
Decompose intervals into sorted start and end events, then sweep a line while maintaining a running counter of active intervals.