Scanline / Event Processing

What type of scanline problems exists

The scanline technique (also called event processing or sweep line) is a powerful algorithmic approach used when working with intervals, segments, rectangles, geometry, timeline events, or any situation where something changes only at discrete points. Instead of checking every possible point, we collect key ``events'', sort them, and then simulate a sweep from left to right (or bottom to top).

This method is widely used for:

• interval coverage and counting active intervals
• finding intersections of segments or rectangles
• solving problems with timeline events (start/end)
• computing union of intervals or area of rectangles
• processing changes in data structures as the sweep pointer moves

The core idea: convert intervals or shapes into ``events'' of the form:

• (position, type, data) Then sort all events by position and simulate what happens between events.

Example 1: Maximum number of overlapping intervals

Problem: Given $n$ intervals $[l_i, r_i]$, find the maximum number of intervals that overlap at any point.