Жадность на отрезках

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

Максимум непересекающихся

Выбрать как можно больше попарно непересекающихся отрезков.

Сортируем по правому концу и берём жадно всё, что не конфликтует с последним взятым.

sort(seg.begin(), seg.end(), [](auto& a, auto& b) { return a.second < b.second; });
int count = 0, last = INT_MIN;
for (const auto& [l, r] : seg)
    if (l >= last) { count++; last = r; }

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

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

Минимум точек, чтобы проколоть все

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

Тот же ключ — правый конец, но алгоритм чуть другой:

sort(seg.begin(), seg.end(), [](auto& a, auto& b) { return a.second < b.second; });
int count = 0, last = INT_MIN;
for (const auto& [l, r] : seg)
    if (l > last) { count++; last = r; }   // ставим точку в r

Разница с предыдущей задачей — один символ: l > last вместо l >= last, потому что точка на границе считается попаданием.

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

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

Покрыть отрезок

Дан отрезок $[0, M]$ и набор отрезков. Выбрать минимальное количество, чтобы покрыть весь $[0, M]$ целиком.

Здесь ключ другой — левый конец. Идём слева направо и на каждом шаге берём тот отрезок, который начинается не позже текущей границы и тянется как можно дальше вправо.

sort(seg.begin(), seg.end());   // по левому концу
int count = 0, covered = 0;
size_t i = 0;
while (covered < M) {
    int best = covered;
    while (i < seg.size() && seg[i].first <= covered)
        best = max(best, seg[i++].second);
    if (best == covered) return -1;   // разрыв, покрыть нельзя
    covered = best;
    count++;
}

Внутренний цикл не сбрасывает i — каждый отрезок рассматривается один раз, поэтому всё вместе линейно после сортировки.

Проверка best == covered обязательна: без неё при разрыве в покрытии цикл становится бесконечным. Это самая частая ошибка в этой задаче.

Объединение отрезков

Слить пересекающиеся отрезки в непересекающиеся.

sort(seg.begin(), seg.end());   // по левому концу
vector<pair<int, int>> merged;
for (const auto& [l, r] : seg)
    if (!merged.empty() && l <= merged.back().second)
        merged.back().second = max(merged.back().second, r);
    else
        merged.push_back({l, r});

max в первой ветке нужен потому, что очередной отрезок может целиком лежать внутри предыдущего. Без него правая граница схлопнется, и часть покрытия потеряется.

Отсюда же считаются суммарная длина покрытия и число «дыр».

Сканирование событий

Когда нужен не сам набор отрезков, а функция «сколько отрезков покрывают точку», переходят к событиям:

vector<pair<int, int>> events;
for (const auto& [l, r] : seg) {
    events.push_back({l, +1});
    events.push_back({r, -1});
}
sort(events.begin(), events.end());

Дальше один проход даёт и максимум покрытия (минимум аудиторий), и точки, где покрытие меняется, и суммарную длину объединения.

Порядок событий при равном времени определяет, считаются ли касающиеся отрезки пересекающимися. Пара {time, delta} сортируется так, что $-1$ идёт раньше $+1$, — это соглашение «отрезки полуоткрыты». Если по условию касание считается пересечением, порядок нужно перевернуть.

Сводка

задача	ключ	что делаем
максимум непересекающихся	правый конец	берём, если не конфликтует
минимум точек-проколов	правый конец	ставим точку в правый конец
покрыть отрезок	левый конец	тянемся как можно дальше
объединить	левый конец	сливаем с последним
максимум одновременных	события	считаем баланс

Правило, которое помогает не перепутать: если нужен максимум объектов — сортируем по правому концу, если нужно покрытие — по левому. В первом случае мы бережём место справа, во втором стараемся уйти вправо как можно дальше.