#algorithm #dynamic-programming #greedy
Вопрос:
Учитывая набор действий с соответствующим временем начала и окончания, определите набор неперекрывающихся действий таким образом, чтобы мощность набора была максимальной.
В CLR было упомянуто, что это можно решить с помощью жадного подхода, сортируя действия на основе времени их завершения (если они еще не отсортированы), а затем жадно выбирая действия. Я попытался погуглить, если есть какой-либо сценарий, при котором жадный подход не может выбрать оптимальное решение. Я не могу найти никаких сценариев.
Мой вопрос так же, как и в задаче с рюкзаком 0/1, где использование жадного подхода не всегда гарантирует оптимальное решение, есть ли какой-либо сценарий, в котором также полезно использовать DP для задачи выбора активности?
Пожалуйста, поделитесь ссылками.
Комментарии:
1. доказательство оптимальности для задачи выбора невзвешенной активности