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

Жадность работает, когда локально лучший шаг ведёт к глобально лучшему ответу.

Жадный алгоритм — стратегия, на каждом шаге делающая локально оптимальный выбор в надежде получить глобальный оптимум.

Когда жадность работает

Не всегда! Жадность корректна только если у задачи есть свойство жадного выбора: локально лучший шаг не закрывает путь к оптимуму. Для размена монет произвольными номиналами жадность может ошибаться, а вот для классических задач планирования — работает и даёт O(n log n) вместо перебора.

Классическая задача: максимум непересекающихся интервалов

Дан набор интервалов (встреч). Сколько максимум можно провести, чтобы они не пересекались? Жадная идея: всегда выбирать встречу, которая раньше всех заканчивается — она оставляет больше места для остальных. Сортируем по правому концу и жадно набираем.

def max_meetings(intervals):
    intervals.sort(key=lambda x: x[1])  # по времени окончания
    count = 0
    last_end = float("-inf")
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

print(max_meetings([(1, 3), (2, 4), (3, 5), (0, 6)]))
print(max_meetings([(1, 2), (2, 3), (3, 4)]))
print(max_meetings([(1, 5), (1, 5), (1, 5)]))

Вывод:

2
3
1

Как работает под капотом

Почему «раньше заканчивается» — правильная жадность? Среди всех совместимых встреч та, что заканчивается первой, оставляет максимум свободного времени дальше. Можно доказать обменом: в любом оптимальном расписании первую встречу можно заменить на самую рано заканчивающуюся, не ухудшив ответа. Дальше задача повторяется на меньшем диапазоне — это и есть оптимальная подструктура плюс жадный выбор. Сортировка даёт O(n log n), сам проход — O(n).

Частые ошибки

• Сортировать по началу или по длительности вместо конца — даёт неоптимальный ответ.
• Применять жадность там, где нужно DP (например, размен произвольными монетами).
• Не доказать жадный выбор и понадеяться «на интуицию» — интервьюер попросит обоснование.

Итог

• Жадность делает локально лучший выбор; корректна не для всех задач.
• В задаче об интервалах сортируйте по концу и набирайте непересекающиеся.
• Готовьтесь обосновать, почему жадный выбор приводит к оптимуму.