Как узнать
оптимум, где на каждом шаге один выбор кажется всегда верным: прыгнуть как можно дальше, взять встречу, которая кончается раньше всех.
Как решать такие задачи
- Назови выбор, который делаешь на каждом шаге: самый дальний прыжок, самый ранний конец, самый дешёвый вариант.
- Проверь, что он безопасен: замена на любой другой выбор не даёт ответа лучше. Если даёт, нужно динамическое программирование.
- Если выбор зависит от порядка, сначала отсортируй: по времени конца, по дедлайну, по размеру.
- Сделай один проход с одним текущим значением и остановись, как только ответ ясен.
Где встречается
- Сжатие. Код Хаффмана в zip, gzip и PNG строится жадно: два самых редких символа склеивают в один, и так снова и снова. Частые символы получают короткие коды, редкие — длинные.
- Маршрутизация. Роутеры с протоколом OSPF строят кратчайшие пути алгоритмом Дейкстры: каждый раз окончательно фиксируют ближайшую ещё не зафиксированную точку и больше к ней не возвращаются.