Geometry & Sweep Line
Turn interval boundaries into ordered events and scan them once.
The idea
Sweep line algorithms replace overlapping ranges with a sorted timeline of start and end events. A running active count changes only at those boundaries, so the scan can answer global overlap questions without checking every pair of intervals.
For half-open intervals, end events must sort before start events at the same coordinate. That tie-break prevents back-to-back intervals from being counted as overlapping.
Move a vertical scanner across a calendar and keep only the meetings intersected by the scanner at its current position.
When to reach for it
- Intervals or geometric objects overlap along one ordered axis.
- The answer changes only at starts, ends, arrivals, or departures.
- Pairwise overlap checks are too expensive.
Language-independent template
events = starts (+1) and ends (-1)
sort events by (coordinate, delta)
active = best = 0
for event in events:
active += event.delta
best = max(best, active)Complexity — time O(n log n), space O(n) (Sorting the 2n boundary events dominates.).
Common mistakes
- Processing a start before an end at the same coordinate for half-open intervals.
- Sorting intervals instead of the individual boundary events.
- Updating the maximum before applying the current event.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Determine whether one person can attend every interval.
Find the minimum number of rooms needed for all meetings.
Compute the visible skyline formed by overlapping buildings.