После сортировки по окончанию выбираются [1,3), [3,4), [5,6): всего три интервала. Раннее завершение оставляет не меньше возможностей для последующих.
Как доказать корректность жадного выбора интервалов
После сортировки по окончанию выбираются [1,3), [3,4), [5,6): всего три интервала. Раннее завершение оставляет не меньше возможностей для последующих.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Из интервалов [1,3), [2,5), [3,4), [4,7), [5,6) нужно выбрать максимум непересекающихся. Разрешено касание границ. Покажите выбор по времени окончания и объясните его.
Ответ
После сортировки по окончанию выбираются [1,3), [3,4), [5,6): всего три интервала. Раннее завершение оставляет не меньше возможностей для последующих.
На каждом шаге выбирайте первый интервал с началом не раньше конца выбранного. В оптимальном решении первый интервал можно заменить самым рано заканчивающимся: число оставшихся совместимых интервалов не уменьшится. Затем применяется тот же аргумент к остатку. Сортировка занимает O(n log n), проход — O(n).