Алгоритмы с нуля
Greedy: планировщик, который можно доказать
Читать про корректность greedy — не то же самое, что защищать greedy-выбор на ревью. Постройте настоящий interval-планировщик, напишите exchange argument, который его обосновывает, затем проверьте его против точного DP-оракула — и намеренно найдите родственную задачу, где greedy доказуемо ошибается, чтобы почувствовать границу между быстрым-и-верным и быстрым-и-неверным.
Превратите дисциплину доказательства из юнита в инженерный цикл: выберите greedy-правило, докажите безопасность его первого выбора через exchange argument, реализуйте его за O(n log n) и проверьте против brute-force или DP-оракула на случайных входах — затем найдите и задокументируйте набор номиналов/весов, где greedy провалится, и объясните, почему ни один exchange не сходится.
Реализуйте и проверьте greedy interval-планировщик, максимизирующий число непересекающихся интервалов, докажите безопасность его greedy choice письменным exchange argument и противопоставьте его родственной задаче (weighted interval scheduling или неканонический набор монет), где greedy доказуемо ошибается и требуется DP.
- Greedy-планировщик совпадает с точным оракулом на каждом из >= 1000 случайных входов, с включённой тестовой обвязкой и фиксированным seed, чтобы прогон воспроизводился.
- Письменный exchange argument явно формулирует факт допустимости (неравенство по времени финиша) и факт не-хуже (один убрали, один добавили, счёт неизменен), плюс рекурсию optimal substructure.
- Для родственной задачи напечатанный контрпример показывает расхождение greedy и DP, с обоими выводами и входом, который его вызывает.
- Короткий разбор называет, у какой задачи есть greedy choice property, а у какой нет, и указывает конкретный swap, проваливающийся в небезопасном случае.
- Добавьте варианты merge-intervals и minimum-rooms (meeting rooms II) и проверьте каждый против независимого оракула, подтвердив, что вы использовали правильный ключ сортировки для каждого (start для merge, sweep по стартам и финишам для комнат).
- Реализуйте weighted interval scheduling с DP за O(n log n) (сортировка по финишу, бинарный поиск последнего совместимого интервала) и покажите на случайной подборке, что невзвешенный greedy ошибается на нём всякий раз, когда веса неравномерны.
- Добавьте property-based тест, генерирующий состязательные наборы интервалов (сильная вложенность, много совпадений по времени финиша), и подтвердите, что greedy всё ещё совпадает с оракулом, задокументировав, как ничьи обрабатываются exchange argument.
- Реализуйте Gas Station и докажите утверждение о безопасности сброса в коде: утверждайте, что для каждого случайного выполнимого экземпляра выживший start завершает круг с баком, ни разу не ушедшим в минус, а невыполнимые экземпляры (суммарный net < 0) возвращают -1.
Это цикл, который вы запускаете всякий раз, когда тянетесь за greedy в продакшене: сформулируйте локальное правило, докажите безопасность его первого выбора через exchange argument (допустимость плюс не-хуже, затем optimal substructure), реализуйте его одним отсортированным проходом и проверьте против точного оракула на случайных входах, прежде чем доверять. Родственный контрпример — вторая половина дисциплины: почувствовать ровно там, где swap проваливается, и есть то, что удерживает вас от выпуска быстрого алгоритма, тихо возвращающего неверный ответ.