Обработка строк сканирования / событий

Какие типы проблем со строками развёртки существуют

Техника сканирующей прямой (также называемая обработкой событий или sweep line) — это мощный алгоритмический подход, используемый при работе с интервалами, отрезками, прямоугольниками, геометрией, событиями на временной шкале или любой ситуацией, где что-то меняется только в дискретных точках. Вместо проверки каждой возможной точки мы собираем ключевые ``события'', сортируем их, а затем имитируем проход слева направо (или снизу вверх).

Этот метод широко используется для:

• покрытия интервалов и подсчёта активных интервалов
• нахождения пересечений отрезков или прямоугольников
• решения задач с событиями на временной шкале (начало/конец)
• вычисления объединения интервалов или площади прямоугольников
• обработки изменений в структурах данных по мере движения указателя сканирования

Основная идея: преобразовать интервалы или фигуры в ``события'' вида:

• (позиция, тип, данные) Затем отсортировать все события по позиции и смоделировать, что происходит между событиями.

Пример 1: Максимальное число перекрывающихся интервалов

Задача: Даны $n$ интервалов $[l_i, r_i]$, найдите максимальное число интервалов, которые перекрываются в любой точке.