Сканирующая прямая - алгоритм, часто применяемый, когда в задаче фигурируют отрезки на прямой или события во времени.

Наибольшее покрытие

Дано $n$ отрезков на прямой, и необходимо найти точку, покрытую наибольшим числом отрезков.

Нетрудно заметить, что среди подходящих точек обязательно будут края отрезков, поэтому рассматривать в качестве ответа можно только их.

Решение в тупую с асимптотикой $O(n^2)$ - перебираем все концы отрезков и для каждого за $O(n)$ считаем количество отрезков, покрывающих данную точку.

Улучшим решение. Можно перебирать края отрезков в порядке увеличения их координаты, поддерживая, сколько отрезков в данный момент “открыто”. Делать это можно с помощью счетчика: если встречаем начало отрезка — $+1$, иначе — $-1$.

Тогда ответом будет та точка, для которой счётчик был наибольшим.

Таким образом мы получим асимптотику $O(n log n)$ из-за сортировки.

Приведём пример кода:

events = []
for a, b in segments:
    events.append((a, -1))
    events.append((b, 1))

events.sort()

cnt = 0
best = 0
ans = -1
for event in events:
    cnt -= event[1]
    if cnt > best:
        best = cnt
        ans = event[0]

print(ans)

Как сортировать события

Стоит сказать пару слов о том, в каком порядке рассматривать события.

Если в одной точке происходит несколько событий разных типов (в нашем случае один отрезок закрылся, а другой открылся), то иногда надо будет сначала открыть новый отрезок, а потом закрыть старый (в нашем случае мы так и делаем, потому что такая точка принадлежит и закрывшемуся отрезку, и открывшемуся). На это влияет порядок сортировки по значению типа события. В данном примере $-1$ — (отрезок открывается), $1$ — (отрезок закрывается).