The Sweep Line Pattern

The sweep line is a powerful technique you have now seen twice. Here is the pattern:

$1.$ Convert intervals to events (start = +1, end = -1 or some action)

$2.$ Sort events by position (time, x-coordinate, etc.)

$3.$ Process events left to right, updating state

$4.$ Track the answer as you sweep It works for counting overlaps, finding maximum depth, computing union length, and many other interval problems. When you see intervals and need to track "at each point," think sweep line.