Жадные алгоритмы и exchange argument: как доказать оптимальность ТЕМА

О чём статья

Жадный алгоритм — самый простой класс алгоритмов олимпиадного программирования: на каждом шаге берём «локально лучшее» и идём дальше. Кажется наивно — и часто работает. Подвох — в доказательстве. Жадный, который «вроде бы работает», ломается на специально подобранных тестах; жадный, обоснованный через exchange argument, гарантированно правильный.

Эта статья — про обоснование. Сам по себе шаблон жадного — две строки кода: отсортировать массив, пробежать. Содержательная часть — какой выбрать ключ сортировки, какой инвариант сохранять, и как доказать, что любое другое решение можно «обменять» на жадное без потери качества. Разбираем шаблон рассуждения на двух классических задачах и одной более сложной с приоритетной очередью.

---

Когда применять: сигналы в условии

Жадный — первая гипотеза, которую стоит проверить на следующих сигналах:

• «Максимизировать / минимизировать сумму / количество» при простой структуре условия. Если задача не упоминает «выбрать $k$ из $n$» с экспоненциальным числом комбинаций, а просто «расположить элементы в порядке X и взять максимум» — жадный работает в 80% случаев.
• «Выбрать максимальное число / минимальный набор» с независимыми условиями. Активити-задачи, упаковочные, расписания.
• Естественный порядок в данных. Если в условии есть «временные интервалы», «отрезки на прямой», «приоритеты» — отсортировать по одному из ключей и пройти один раз часто даёт правильный ответ.
• Маленькая структура состояния. Если в задаче нет «зависимостей между выборами» — нет необходимости в DP, жадный точно работает.

Если хотя бы один сигнал есть — стоит попробовать обосновать жадный через exchange argument. Если доказательство не складывается — это сильный сигнал, что задача не жадная, и нужно DP или другой подход.

---

Базовый шаблон рассуждения (Exchange argument)

Exchange argument — стандартный приём доказательства оптимальности жадного. Структура — четыре шага:

1. Сформулировать жадный. Какой ключ сортировки, какой инвариант сохраняется.
2. Допустить контрпример. Пусть существует решение $\textit{OPT}$, отличающееся от жадного $\textit{GR}$ и при этом строго лучше (или равно).
3. Найти «обмен». Показать, что в $\textit{OPT}$ есть пара элементов, которые можно поменять местами / заменить на «жадные», и стоимость не вырастет.
4. Сделать вывод. Цепочка обменов превращает $\textit{OPT}$ в $\textit{GR}$, не ухудшая. Значит, $\textit{GR}$ — оптимален.

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

---

Задача-иллюстрация 1: максимальное число непересекающихся интервалов (~CF 1200)

Условие

Дано $n$ интервалов $[s_i, e_i]$ на прямой (целочисленные концы). Найти максимальное число попарно не пересекающихся интервалов, которые можно выбрать. Два интервала $[s_1, e_1]$ и $[s_2, e_2]$ не пересекаются, если $e_1 \le s_2$ или $e_2 \le s_1$ (касание считается допустимым).

Сигнал и жадный

«Выбрать максимальное число элементов» + «независимые условия». Жадный: отсортировать интервалы по правому концу $e_i$ возрастанию. Идти по списку и брать каждый интервал, чей левый конец $\ge$ правого конца последнего выбранного.

Доказательство через exchange argument

1. Жадный (GR): на каждом шаге берём интервал с минимальным правым концом среди тех, что не пересекаются с уже взятыми.
2. Допущение: пусть существует $\textit{OPT}$ с большим числом интервалов.
3. Обмен. Пусть в $\textit{OPT}$ первый по правому концу интервал — $I^*$, а в $\textit{GR}$ — $G_1$. По жадному правилу $e_{G_1} \le e_{I^*}$. Заменим $I^*$ на $G_1$ в $\textit{OPT}$ — это не сломает $\textit{OPT}$: все остальные интервалы в $\textit{OPT}$ начинаются после $e_{I^*} \ge e_{G_1}$, значит, не пересекаются и с $G_1$.
4. Рекурсия. По тому же аргументу — заменяем второй интервал в $\textit{OPT}$ на $G_2$, и т.д. В конце $\textit{OPT}$ становится $\textit{GR}$ — без изменения числа интервалов. Значит, $|\textit{GR}| \ge |\textit{OPT}|$. ∎

Псевдокод

отсортировать интервалы по возрастанию e_i
cnt ← 0
last_end ← -∞
для (s, e) из отсортированного списка:
    если s ≥ last_end:
        cnt ← cnt + 1
        last_end ← e
вернуть cnt

Код

Что характерно

• Ключ сортировки — нетривиальный. Естественные кандидаты: длина интервала, левый конец, центр. Все они дают неверные жадные. Только сортировка по правому концу — корректна.
• Exchange argument — обоснование выбора ключа. Если попытаться доказать по другому ключу — обмен не пройдёт (можно построить контрпример).
• Сложность: $O(n \log n)$ на сортировку, $O(n)$ на проход.

---

Задача-иллюстрация 2: минимальная стоимость слияния (~CF 1400)

Условие

Дано $n$ «верёвок» длинами $a_1, \ldots, a_n$. За одну операцию можно взять две верёвки длины $x$ и $y$, склеить в одну длины $x + y$, заплатив стоимость $x + y$. Нужно склеить все верёвки в одну за минимальную суммарную стоимость.

Ограничения. $1 \le n \le 10^5$, $1 \le a_i \le 10^9$.

Сигнал и жадный

«Минимизировать суммарную стоимость» + «структура операций повторяющаяся». Жадный: на каждом шаге склеивать две самые короткие верёвки.

Реализация — через min-heap (приоритетная очередь): извлекаем два минимума, добавляем их сумму обратно в кучу, прибавляем к ответу.

Доказательство через exchange argument

Понятно, что выбор пары для слияния влияет на глубину включений: длина каждого исходного $a_i$ войдёт в финальную сумму ровно depth(a_i) раз, где depth — глубина в «дереве слияний». Цель — минимизировать $\sum_i a_i \cdot \text{depth}(a_i)$, что эквивалентно: длиннее элементы должны быть выше в дереве.

Жадный «склеивать два минимума» строит полное дерево слияний снизу вверх так, что глубина $a_i$ обратна $a_i$ — длинные элементы оказываются ближе к корню.

Exchange argument: допустим, в оптимальном дереве два самых коротких $a_i, a_j$ оказались не на одном самом глубоком уровне. Тогда есть какой-то лист $a_k$ на самом глубоком уровне с $a_k > a_i$ или $a_k > a_j$. Поменяем $a_k$ и $a_i$ местами — глубина $a_i$ увеличилась, глубина $a_k$ уменьшилась. Поскольку $a_k > a_i$, $a_k \cdot (\text{новая глубина}) + a_i \cdot (\text{новая глубина}) \le a_k \cdot (\text{старая глубина}) + a_i \cdot (\text{старая глубина})$. Стоимость не выросла. Значит, можно превратить любое оптимальное дерево в жадное. ∎

Это — упрощённая форма доказательства, общая идея пришла из конструкции Huffman.

Псевдокод

heap ← min-heap из всех a_i
cost ← 0
пока |heap| > 1:
    x ← heap.pop_min()
    y ← heap.pop_min()
    cost ← cost + (x + y)
    heap.push(x + y)
вернуть cost

Код

Что характерно

• Структура данных — приоритетная очередь. Сортировки одной не хватает: после каждого слияния новый элемент должен встать в правильное место.
• Стоимость не очевидна из формулы. «Сумма по слияниям» зависит от порядка слияний — это структурная задача, а не «отсортировать и пройти».
• Exchange argument сложнее. Прямого «поменять два элемента» недостаточно — нужно понимать, что мы меняем глубины в дереве слияний.
• Сложность: $O(n \log n)$ — $n - 1$ извлечений и вставок из кучи размера $\le n$.

---

Задача-иллюстрация 3: расписание задач с дедлайнами и штрафами (~CF 1600)

Условие

Дано $n$ задач. Каждая задача занимает ровно 1 единицу времени. Задача $i$ имеет дедлайн $d_i$ (целое, $1 \le d_i \le n$) и штраф $p_i$ за невыполнение в срок. Можно выполнять задачи в произвольном порядке, но в каждую единицу времени — ровно одну. Задача считается выполненной в срок, если она поставлена в слот $\le d_i$. Минимизировать сумму штрафов за задачи, не выполненные в срок.

Сигнал и жадный

«Минимизировать штраф» + «независимые единицы времени». Жадный: отсортировать задачи по убыванию штрафа. По очереди — пытаемся занять самый поздний свободный слот $\le d_i$. Если такого слота нет — задача не выполняется, штраф добавляется к ответу.

Доказательство через exchange argument

Допустим, есть оптимальное расписание $\textit{OPT}$, отличающееся от жадного. Возьмём первое расхождение: жадный поставил задачу $A$ с наибольшим штрафом в слот $t$, а $\textit{OPT}$ — какую-то задачу $B$ (или оставил слот пустым). Тогда:

• Если $A$ в OPT не выполнена (пропущена), а $B$ выполнена в $t$: уберём $B$ из слота $t$, поставим $A$. Штраф уменьшился на $p_A - p_B \ge 0$.
• Если $A$ в OPT выполнена в другом слоте $t' < t$, а в $t$ стоит $B$: поменяем $A$ и $B$ местами. Оба остаются в срок ($A$ — потому что слот $t \le d_A$ по жадному правилу; $B$ — потому что $t' < t \le d_B$ в $\textit{OPT}$). Штрафы не изменились.

Цепочка таких обменов превращает $\textit{OPT}$ в жадный, не увеличив штраф. ∎

Псевдокод

отсортировать задачи по убыванию p_i
occupied[1..n] ← все False
penalty ← 0
для (d, p) из отсортированного списка:
    slot ← -1
    для t от min(d, n) до 1 (шаг -1):
        если не occupied[t]:
            slot ← t
            прервать
    если slot = -1:
        penalty ← penalty + p
    иначе:
        occupied[slot] ← True
вернуть penalty

Простой поиск свободного слота — $O(n)$ на задачу, итого $O(n^2)$. На $n \le 10^3$ — приемлемо. На больших $n$ — заменить на DSU (disjoint set union) с операцией «найти ближайший свободный слот $\le t$», что даёт $O(n \cdot \alpha(n))$.

Код

Что характерно

• Ключ сортировки — штраф, не дедлайн. Естественная гипотеза «сортировать по дедлайну» не работает.
• Поиск слота — с самого позднего. Это сохраняет ранние слоты для задач с меньшими дедлайнами, которые ещё придут.
• Сложность: $O(n^2)$ простая, $O(n \log n)$ с DSU. На $n = 10^5$ — нужен DSU.

---

Типичные ошибки

1. «Очевидный» ключ сортировки. Самая частая ошибка: взять первую попавшуюся сортировку (по длине, по началу, по сумме координат), запустить, получить WA. Лекарство — придумать exchange argument до написания кода. Если не сложился — ключ неправильный.

2. Жадный там, где нужен DP. Если задача спрашивает «выбрать $k$ из $n$ так, чтобы сумма / произведение / ... было оптимально» — почти всегда DP. Жадный работает только при независимых выборах. Тест: можно ли построить контрпример на $n = 4, 5$, где жадный даёт неоптимум?

3. Перепутать min/max в обмене. В доказательстве exchange argument: меняем какой элемент на какой, и в какую сторону растёт стоимость? Аккуратность с неравенствами — простая, но частая ошибка.

4. Не доказать монотонность ключа. Сортировка по «весу/времени» или «штрафу/дедлайну» (комбинированный ключ) — нужно отдельно доказать, что именно этот ключ даёт правильный порядок. Иногда комбинация неочевидна (Smith's rule в shop scheduling).

5. Структура данных — не приоритетная очередь. При $n$ слияниях нужна именно куча; сортировкой не обойтись (после каждого слияния новый элемент должен попасть в нужное место). Замена кучи на отсортированный массив с поиском вставки — $O(n^2)$ вместо $O(n \log n)$.

6. Жадный «по двум осям». Когда у задачи два параметра (например, «вес» и «значение») — простая сортировка по одному не работает, нужна по комбинированному критерию (например, «значение/вес»). Без доказательства это часто WA.

7. Жадный с заглядыванием на $k$ шагов вперёд. «Берём не самое выгодное сейчас, а с учётом следующих двух шагов» — это уже не жадный, а DP. Если действительно нужно — переходим к DP, не маскируем под жадный.

---

Когда жадный НЕ подходит

• Сильные зависимости между выборами. Если выбор в шаге $i$ влияет на доступность вариантов в шаге $i + k$, $k > 1$ — почти наверняка DP.
• Сложная функция стоимости. Когда стоимость зависит не от отдельных элементов, а от пар или подмножеств взаимодействующих — жадный обычно ломается.
• Подсчёт количества решений. Жадный находит одно оптимальное решение; для подсчёта всех — DP.
• Задачи с обратной связью. Например, «выбрать подмножество, затем …» — обычно это DP по подмножествам или поток.

---

Связанные техники

• Бинпоиск по ответу с жадной проверкой. Внутри can(x) часто стоит жадный алгоритм. См. тему «Бинпоиск по ответу» этой же серии и стратегию по бинпоиску.
• DP вместо жадного. Когда жадный неверен. См. тему «Динамическое программирование: базовые шаблоны».
• Сортировка + проход. Базовый паттерн жадного. Эта статья — обобщение этого паттерна.
• Приоритетная очередь. Структура данных для жадного с динамическим выбором минимума / максимума.
• DSU (disjoint set union) — для эффективного «следующего свободного слота» в задачах вроде расписания со штрафами.

---

Итого

• Идея жадного: на каждом шаге выбираем локально лучшее, никогда не откатываемся.
• Главная техника доказательства: exchange argument — заменить любое отличающееся решение на жадное цепочкой обменов без потери качества.
• Шаблон: отсортировать по правильному ключу + один проход (или приоритетная очередь для динамики).
• Типичный критерий: «локально лучшее» + «независимость выборов» + «доказуемый exchange argument».
• Когда не подходит: зависимости между выборами, сложные функции стоимости, подсчёт количества решений, обратная связь.
• Главные ловушки: «очевидный» ключ сортировки без доказательства, жадный там, где нужен DP, путаница в exchange argument.