Как уместить больше встреч? — разбор задачи

Условие

В один день предлагают шесть встреч: $A$ — $09{:}00$ – $10{:}30$ $B$ — $09{:}30$ – $10{:}00$ $C$ — $10{:}00$ – $11{:}00$ $D$ — $10{:}30$ – $12{:}00$ $E$ — $11{:}00$ – $12{:}00$ $F$ — $12{:}00$ – $13{:}00$ Нужно посетить каждую выбранную встречу целиком. Две встречи совместимы, если первая заканчивается не позже начала второй; времени на переход не требуется. Все встречи одинаково ценны. Как посетить наибольшее число встреч? Предложите правило выбора, применимое и к другим таким спискам.

О задаче · Подростки и взрослые

Тема: Жадные алгоритмы
Для кого: Подростки и взрослые
Уровень библиотеки: Следующий шаг · ориентир

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Раннее окончание оставляет больше возможностей после встречи.

Подсказка 2

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

Разобрать решение по шагам

Составьте план

Раньше всех заканчивается $B$ в $10{:}00$ После неё из оставшихся совместимых раньше всех заканчивается $C$ затем выбираем $E$ и $F$ Получаем четыре встречи: $B$ $C$ $E$ $F$ Совпадение конца одной и начала следующей разрешено условием.

Докажите правило обменом

Рассмотрим любой оптимальный план и его первую встречу $X$ Встреча $Y$ с самым ранним окончанием заканчивается не позже $X$ Заменим $X$ на $Y$ все последующие встречи, начинавшиеся после $X$ по-прежнему можно посетить. Значит, существует оптимальный план, начинающийся с $Y$ После её выбора та же задача остаётся для встреч, начинающихся не раньше её конца; рассуждение повторяется.

Проверьте максимум для этого списка

Независимо от общего доказательства можно быстро получить верхнюю границу. Из пары $A$ и $B$ одновременно взять обе нельзя. Из пары $C$ и $D$ тоже нельзя взять обе. В этих двух парах четыре разных встречи. Значит, из шести встреч нужно пропустить хотя бы две: больше четырёх невозможно. Наш план эту границу достигает.

План с последовательными окончаниями

01B → C09:30–10:00 → 10:00–11:00

02E → F11:00–12:00 → 12:00–13:00

034 встречини одного пересечения

Ответ

$4$ встречи: $B,C,E,F$

Главная идея

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

Как заметить эту идею в другой задаче

Нужно выбрать максимум непересекающихся интервалов, а все встречи одинаково ценны. Самое раннее окончание оставляет не меньше места для последующих; объясните это обменом.

Возможная ошибка

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

Источник и примечания

Источник и редакция

Авторская учебная задача на классическую идею. Формулировка и разбор — Popov Academy.

Проверь себя

В список добавили $G$ — $08{:}00$ – $09{:}00$ Как изменится максимум?

Ответ к дополнительной задаче

Получится пять встреч: $G$ $B$ $C$ $E$ $F$ $G$ совместима с прежним планом, а больше пяти нельзя: среди исходных шести по-прежнему можно выбрать не больше четырёх.

Продолжить тему: Поиск и алгоритмы →

Тема, знания и приёмы

Поиск и алгоритмы · Нужна школьная база

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

Приёмы решения: Обоснованный жадный выбор

Задать вопрос по задаче →

Условие

Составьте план

Докажите правило обменом

Проверьте максимум для этого списка

Источник и редакция

Условие

Дополнительная задача