Классические жадные задачи

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

Расписание: максимум непересекающихся отрезков

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

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

Очередь: минимум суммарного ожидания

Одна касса, известно время обслуживания каждого. Порядок выбираем мы, минимизируем сумму времён ожидания.

Сортировать по возрастанию времени обслуживания.

Почему. Время $t_i$ входит в ответ ровно столько раз, сколько человек стоит после $i$-го. Значит, чем дольше обслуживание, тем меньше людей должно ждать за ним, — то есть длинные в конец.

Проверить себя дешевле, чем спорить: на входе 1 100000 порядок «сначала долгий» даёт ожидание 100000, обратный — 1.

Пары по близости

Разбить людей на пары так, чтобы разница внутри пары не превосходила $d$, и пар было как можно больше.

Отсортировать и объединять соседей: подходит пара — взяли и шагнули на два, не подходит — шагнули на один.

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

Как ломается наивная версия. Искать каждому «первого подходящего» без сортировки — тогда кто-то заберёт себе того, кто был нужен другому.

Пары с минимальным максимумом

Разбить $n$ человек на пары так, чтобы наибольшая сумма пары была наименьшей.

Отсортировать и объединять первого с последним, второго с предпоследним.

Почему. Если самый сильный стоит не с самым слабым, обмен партнёрами не увеличивает максимум — классический обменный аргумент.

Две шеренги

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

Отсортировать оба и сопоставить по порядку.

Почему. Если две пары «перекрещены», их расплетение не увеличивает сумму. Это проверяется разбором четырёх случаев взаимного расположения и переносится по индукции.

Точка встречи

Точка на прямой, минимизирующая сумму расстояний до заданных точек, — это медиана, а не среднее.

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

Среднее минимизирует сумму квадратов расстояний. Это другая задача с другим ответом, и путают их постоянно.

Что общего

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