Где применяется
1. Задача
У тебя одна переговорная и стопка заявок на бронь. У каждой заявки есть время начала и время конца. Некоторые заявки пересекаются: бронь с 9 до 11 и бронь с 10 до 12 в одну комнату вместе не поставить. Нужно принять как можно больше заявок так, чтобы комната ни разу не была занята дважды.
Так же устроены рекламный экран с одним слотом на показ и одна машина с очередью задач. Ресурс один, заявок много, у каждой своё время, и нужно обслужить как можно больше.
Самые очевидные правила проигрывают. Возьми заявки [0,30], [5,10], [15,20]. Если брать ту, что начинается раньше всех, возьмёшь [0,30], и она закроет обе остальные: одна встреча вместо двух. Если брать самую короткую, тоже можно ошибиться: из [1,5], [4,7], [6,10] самая короткая [4,7], и она пересекается с обеими соседками. Всегда работает ровно одно правило, о нём этот урок.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- наименьшее число монет или частей на сумму
- берём самую крупную, что ещё помещается
- выдать сдачу номиналами
- доказать оптимальность обменным аргументом
Похоже, но не то
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Динамика держит все варианты открытыми до конца. Жадность выбирает сразу и не может откатиться.
- Бэктрекинг (Backtracking)
Бэктрекинг пробует все варианты и оставляет лучший. Жадность пробует один и ему верит.
- Сортировка с пользовательским компаратором (Sort with a custom comparator)
Большинство жадных решений начинается с сортировки. В компараторе и записан сам выбор.
- Бинарный поиск по ответу (Binary search on the answer)
Там сама проверка часто жадная. Поиск лишь выбирает значение для проверки.
O(n log n), если вход сначала нужно отсортировать. Проход после сортировки это один цикл, O(n).
На LeetCode
Задачи, где нужно оставить больше всего непересекающихся отрезков или убрать меньше всего, чтобы остальные не пересекались. Отсортируй по концу и оставляй каждый отрезок, который начинается не раньше конца последнего оставленного.
Запусти жадный алгоритм урока и верни, сколько отрезков он пропустил. Касание здесь не считается пересечением, как и в уроке.
Стреляй в конец первого по концу шарика, и все шарики, которые начинаются в этой точке или раньше, лопнут тоже. Касающиеся шарики здесь лопаются одной стрелой, так что новая стрела нужна, только когда начало больше последнего конца.
Цепочка это набор пар без пересечений, так что сортировка по второму числу и жадный выбор дают самую длинную. Следующая пара должна начинаться строго после конца предыдущей.
Каждое событие занимает один день, поэтому иди по дням, клади концы начавшихся событий в мин-кучу, выбрасывай прошедшие и посещай то, что кончается раньше всех.