Баланс: сколько отрезков покрывает точку

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

Наивно: перебрать все целые координаты и для каждой пересчитать покрытие — $O(Cn)$, где $C$ — размер координатной сетки. При координатах до $10^9$ это безнадёжно.

Решение

Покрытие меняется только в точках открытия и закрытия. Между ними оно постоянно — значит, проверять нужно только их.

Заведём переменную баланс — число открытых на данный момент отрезков.

int balance = 0, best = 0;
long long bestX = 0;
for (const Event& e : events) {
    balance -= e.type;                 // -1 открытие → +1, +1 закрытие → -1
    if (balance > best) { best = balance; bestX = e.x; }
}

Всё решение — четыре строки после сортировки. Сложность $O(n \log n)$.

Проверено: на тридцати тысячах случайных наборов до семи отрезков максимум покрытия совпал с прямым перебором координат.

Максимум обновляется после изменения баланса и только на открытиях — на закрытии баланс убывает, и новый рекорд там появиться не может. Отдельно это проверять не нужно, if и так не сработает.

Аналогия со скобками

Это ровно проверка правильной скобочной последовательности: открытие — открывающая скобка, закрытие — закрывающая, баланс — тот же баланс.

Отличия два. Во-первых, здесь баланс не обязан возвращаться к нулю в промежутках. Во-вторых, скобки не обязаны быть правильно вложены — отрезки могут пересекаться как угодно.

Но техника та же, и полезно это помнить: как только в задаче появляется «сколько чего-то активно в данный момент», думайте про баланс.

Что ещё считается тем же проходом

Число различных значений покрытия. Или, скажем, суммарная длина участков, покрытых ровно $k$ отрезками:

long long prev = 0;
vector<long long> lengthByDepth(n + 1, 0);
for (const Event& e : events) {
    lengthByDepth[balance] += e.x - prev;   // участок до текущего события
    prev = e.x;
    balance -= e.type;
}

Здесь важно прибавлять длину до изменения баланса: на участке от предыдущего события до текущего действовало старое значение.

Максимальное число одновременных занятий. Классическая формулировка «сколько аудиторий нужно» — это в точности максимум баланса, и она разобрана в разделе про жадность.

Момент, когда покрытие стало равно нулю. Признак того, что закончилась одна «связная группа» отрезков; на этом строится объединение.

Отрезок, а не точка

Часто нужна не одна точка максимума, а весь участок, где покрытие максимально. Он тоже получается за тот же проход: запоминаем координату, где баланс достиг максимума, и координату следующего события.

Осторожно с типом отрезка: для замкнутых участок максимума может выродиться в точку (когда один отрезок кончается ровно там, где другой начинается), и это правильный ответ, а не ошибка.

Когда баланса мало

Баланс — это одно число, и он отвечает только на вопрос «сколько». Если нужно знать, какие именно отрезки сейчас открыты, вместо счётчика заводят множество:

set<int> active;
// на открытии: active.insert(e.id);
// на закрытии: active.erase(e.id);

Это дороже — логарифм на событие вместо константы, — зато позволяет отвечать на вопросы вида «какой из активных отрезков самый длинный» или «есть ли среди активных отрезок с таким-то свойством».

Промежуточный вариант: держать не множество, а одну агрегированную величину — например, максимальную правую границу среди открытых. Часто этого достаточно, и константа остаётся маленькой.