Жадные алгоритмы

Greedy algorithms делают locally best choice и не возвращаются к нему. Они привлекательны из-за маленькой реализации, но correctness требует доказательства: exchange argument, staying-ahead invariant или matroid-like property, делающая local choices безопасными.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Ожидайте interval scheduling, coin-like choices, jump games и sorting by key перед одним проходом. Объясните, почему выбранный order не произволен.

Типовые ошибки: Greedy-looking решение может упасть, когда early choice блокирует better future. Ищите counterexample до финального выбора, особенно для knapsack-like problems.

Чеклист:

• Назовите local choice.
• Докажите exchange или invariant.
• Сортируйте по правильному key.
• Проверьте counterexamples.