Loading...
Loading...
Tier III · Advanced
Processing sorted event points to answer geometric and interval questions.
A line sweep turns every interval into two events, a where it starts and a where it ends, sorts them, and walks them left to right with a running count. Nothing changes between two events, so looking only at the events never misses the answer.
start, +1end, −1touching the line
count 0max 0
Every start and every end becomes an event. The line visits them in order.
Watch the line cross the bars. Each one lights up while the line touches it, and the count only moves when the line lands on a start or an end, so one pass over the sorted events finds the peak.
| Variant | What the sweep carries | Typical use |
|---|---|---|
| Counter | One integer, or | Peak overlap, capacity checks |
| Heap of open intervals | Which ones are still running | Assigning groups, tallest height |
| Two sorted lists | Sorted starts and ends | How many cover a query point |
The usual slip is ties. When one interval ends at 4 and another starts at 4, the order you process those two events decides whether they overlap, so starts go first for closed intervals and ends go first for half-open ones. And once the sweep has to know which interval just ended, a counter stops being enough and the state becomes a heap.
| Approach | Time | Extra space |
|---|---|---|
| Count at every start, every interval | ||
| Sort the events, one sweep | ||
| Difference array over small coordinates |
Use it when a problem asks how many things are happening at once, whether a load ever goes over a limit, which resource frees up next, or how an outline changes as you move along a line.
The problems below start with counting peak overlap and covered points, move through weighted loads and assigning intervals to groups with a heap, and end with point queries by binary search and the skyline outline.
Recommended first: Merge Intervals, Binary Search.
You've cleared 0 of 14 problems in these. You can dive in anyway.