Sweep Line Algorithms

Many problems that look like they need comparing every pair of items — do any two time intervals overlap, do any two line segments cross, what's the maximum number of overlapping bookings at any moment — can instead be solved by imagining a vertical line sweeping across the data from left to right, stopping only at points where something changes, called events. Rather than testing every pair directly, the sweep processes events in sorted order and maintains a small, running summary of "what's currently active" at the sweep line's position, updating that summary incrementally as each event is reached.

A classic example is finding the maximum number of overlapping meetings from a list of start and end times: convert each meeting into a "+1" event at its start and a "-1" event at its end, sort all the events by time, then sweep through them left to right maintaining a running counter, adding one at each start event and subtracting one at each end event. The counter's peak value across the whole sweep is exactly the maximum overlap, computed in time proportional to sorting the events rather than comparing every pair of meetings against each other.

This pattern — turn the problem into sorted events, sweep through maintaining a running state — comes up constantly in coding interviews (overlapping intervals, meeting rooms, skyline problems) and directly mirrors how an order book processes a sequence of order arrivals and cancellations in timestamp order.