События и порядок сортировки

Большинство задач про отрезки на прямой решаются одной схемой:

1. Каждый отрезок $[l, r]$ разбить на два события — «открылся в $l$» и «закрылся в $r$».
2. Отсортировать все события по координате.
3. Пройти по ним слева направо, поддерживая какое-то состояние.

Приём называется сортировкой событий, или сканирующей прямой: мы как будто ведём вертикальную линию слева направо и смотрим, что она пересекает.

Идея в том, что между двумя соседними событиями ничего не меняется. Значит, перебирать все координаты незачем — достаточно $2n$ интересных точек.

Событие — это структура

Первое, о чём стоит договориться, — как событие хранить.

struct Event {
    long long x;   // координата
    int type;      // -1 открытие, +1 закрытие
    int id;        // номер отрезка
};

Не pair<long long, pair<int, int>> и не tuple. Причины разобраны в статье про свои структуры, и в этой теме они особенно заметны: полей у события обычно три-четыре, и через месяц никто не вспомнит, что такое e.second.first.

Добавить поле в структуру — одна строка. Добавить его в пару пар — переписать всё решение.

Порядок при разных координатах

Тут вопросов нет: по возрастанию $x$.

Порядок при совпадающих координатах

А вот это — единственное место, где нужно думать, и оно зависит от задачи.

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

Замкнутые отрезки $[l, r]$. Точка стыка принадлежит обоим, значит в ней покрытие равно двум. Чтобы баланс это увидел, открытие должно обрабатываться раньше закрытия.

Полуинтервалы $[l, r)$. Точка стыка принадлежит только второму отрезку, покрытие равно единице. Значит, закрытие раньше открытия.

Клетки. Если отрезок задан номерами клеток «с $l$-й по $r$-ю включительно», удобнее сразу перейти к полуинтервалу $[l, r+1)$ и дальше не думать.

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

Трюк со знаками

Дальше — приём, который убирает половину if.

Закодируем тип события числом: открытие $-1$, закрытие $+1$. Тогда, во-первых, сортировка по типу автоматически ставит открытия раньше закрытий (потому что $-1 < +1$). Во-вторых, изменение баланса пишется без ветвления:

balance -= e.type;   // открытие: +1, закрытие: -1

Если нужен обратный порядок (полуинтервалы), знаки меняются местами: открытие $+1$, закрытие $-1$, и баланс становится balance += e.type.

Компаратор при этом сводится к двум строкам:

sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.type < b.type;
});

Или, если вы предпочитаете tie:

return tie(a.x, a.type) < tie(b.x, b.type);

Обе записи задают строгий порядок, что для sort обязательно.

Каркас

vector<Event> events;
for (int i = 0; i < n; i++) {
    events.push_back({l[i], -1, i});
    events.push_back({r[i], +1, i});
}
sort(events.begin(), events.end(), cmp);

int balance = 0;
for (const Event& e : events) {
    balance -= e.type;
    // здесь состояние актуально для точки e.x
}

Дальше вся разница между задачами — в том, что делать внутри цикла. Максимум покрытия, объединение, вложенность — это три разных тела одного и того же цикла.

Сложность

$O(n \log n)$ — вся стоимость в сортировке; проход линеен.

Если координаты маленькие, сортировку можно заменить на сортировку подсчётом и получить честную линию. На практике это редко нужно.

Если координаты огромные, а важен только порядок, помогает сжатие координат — но для самой схемы событий оно и не требуется: мы и так работаем только с $2n$ точками.