Дуги на окружности

Задача о кассах: каждая работает с $l_i$ до $r_i$ в течение суток. Найти момент, когда работает больше всего касс.

Пока $l_i < r_i$, это обычная задача про отрезки. Но касса может работать с 22:00 до 6:00 — и такой «отрезок» переходит через полночь.

Геометрически это дуга на окружности, а не отрезок на прямой. Прямые методы к ней неприменимы.

Способ первый: разрезать и разделить

Разрежем окружность в нуле и развернём в отрезок $[0, T)$, где $T$ — длина суток.

Обычные дуги перейдут в обычные отрезки. Дуга, пересекающая разрез, распадётся на две части: $[l, T)$ и $[0, r)$.

for (int i = 0; i < n; i++) {
    if (l[i] < r[i]) {
        add(l[i], r[i]);
    } else {                       // переходит через полночь
        add(l[i], T);
        add(0, r[i]);
    }
}

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

Ловушка. Если требуется не максимум покрытия, а, скажем, «участок, покрытый всеми $n$ дугами», разрезанная дуга не должна считаться дважды. Баланс при этом остаётся верным: обе части не пересекаются, так что в любой точке добавляется не больше единицы. Но если вы храните множество активных отрезков, один и тот же идентификатор появится в двух местах — это надо учесть.

Способ второй: удвоить

Рассмотрим отрезок длины $2T$ — «двое суток подряд».

Обычные дуги выпишем дважды: как $[l, r]$ и как $[l + T, r + T]$. Дуги, переходящие через разрез, выпишем один раз посередине: как $[l, r + T]$.

for (int i = 0; i < n; i++) {
    if (l[i] < r[i]) {
        add(l[i], r[i]);
        add(l[i] + T, r[i] + T);
    } else {
        add(l[i], r[i] + T);
    }
}

Теперь любая дуга представлена целым отрезком, ничего не разрывается. Ответ ищется на средней части — на промежутке $[T, 2T)$.

Этот способ дороже по памяти, но незаменим, когда важна целостность дуги: например, если нужно вывести саму дугу или знать, какая дуга где активна.

Какой выбрать

нужно	способ
максимум покрытия, длина объединения	разрезать (проще)
работать с дугой как с целым	удвоить
вывести конкретную дугу-ответ	удвоить
дуга может обойти круг целиком	обработать отдельно

Последняя строка — вырожденный случай, который легко пропустить: касса, работающая круглосуточно. Формально $l = r$, и обе схемы дадут неверный ответ. Такие дуги стоит отфильтровать заранее и добавить их вклад к балансу как константу.

Сколько может быть участков ответа

Полезный факт: на окружности с $n$ дугами участков, покрытых всеми дугами сразу, не больше $n$.

Причина в том, что каждая граница участка обязана быть началом или концом какой-то дуги, а границ ровно $2n$; при этом участки чередуются с непокрытыми промежутками, так что их не больше $n$.

Это важно для оценки: перебирать все участки допустимо, их немного.

Родственные постановки

Кратчайшая дуга, покрывающая все точки. Разворачиваем окружность, удваиваем, дальше два указателя по точкам.

Максимум точек в дуге заданной длины. То же самое: удвоение плюс окно.

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

Общий совет: как только в условии появилось слово «циклически» или «по кругу», думайте про удвоение. Приём работает и для массивов: циклический подмассив ищется в удвоенном массиве обычным окном.