Доказательство обменом

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

Задача о расписании

Дано $n$ заявок на переговорную, каждая занимает промежуток $[l_i, r_i]$. Две заявки нельзя удовлетворить вместе, если промежутки пересекаются. Найти наибольшее число заявок.

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

sort(segments.begin(), segments.end(),
     [](auto& x, auto& y) { return x.second < y.second; });

int taken = 0, lastEnd = INT_MIN;
for (auto& [from, to] : segments)
    if (from > lastEnd) { taken++; lastEnd = to; }

Почему по правому концу, а не по левому и не по длине? Ответ даёт обмен.

Оптимальный алгоритм как чёрный ящик

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

1. её ответ допустим;
2. лучше её ответа не бывает.

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

Сам обмен

Пусть оптимальный ответ $O$ и наш ответ $A$ упорядочены по правому концу. Если они совпадают — доказывать нечего. Иначе посмотрим на первое место, где они различаются.

Всё, что до этого места, у них общее. Значит, обе заявки — и та, что взял оптимальный, и та, что взяли мы, — совместимы со всем общим началом.

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

Теперь заменим в оптимальном ответе его заявку на нашу. Что изменится?

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

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

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

Остаётся длина

А вдруг оптимальный длиннее — в нём есть заявка, которой у нас нет?

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

Ответы совпали по размеру, а размер — это и есть ответ задачи.

Схема, которую можно повторять

Приём общий и почти всегда выглядит одинаково:

1. Взять оптимальный ответ и наш, упорядочить одинаково.
2. Найти первое место, где они расходятся.
3. Показать, что выбор нашего алгоритма можно подставить в оптимальный, не ухудшив его.
4. Заключить по индукции, что наш ответ не хуже.

Ключевой — третий шаг, и именно в нём используется то самое свойство, по которому мы сортировали. Если подстановка не проходит, значит, ключ сортировки выбран неверно, и это сигнал искать контрпример.

Почему не по длине и не по левому концу

Попробуйте провести тот же обмен для сортировки по длине — он не пройдёт, и контрпример находится сразу. Заявки $[1,5]$, $[4,6]$, $[6,10]$: самая короткая — $[4,6]$, она перекрывает стык двух других. Жадность по длине берёт одну заявку, правильный ответ — две.

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