Жадный алгоритм для выбора активностей: как решать задачи с интервалами

Почему стоит освоить жадный алгоритм для выбора активностей?

Вы когда-нибудь застревали на задаче составления расписания, перебирая все возможные комбинации? Я помню, как готовился к техническому собеседованию и часами смотрел на доску с интервалами встреч, думая: «Должен же быть способ умнее, чем полный перебор». Мозг кипел от брутфорса с backtracking, а каждая попытка напоминала удары в закрытую дверь. Кофе остыл, а тиканье таймера интервьюера становилось всё громче.

В тот момент возник вопрос: есть ли правило, позволяющее выбрать «лучший» следующий шаг без заглядывания вперёд? Ответ — в жадном подходе, и задача выбора активностей — идеальный полигон для его отработки.

Суть жадного подхода: выбираем самую раннюю завершающуюся активность

Хитрость жадного алгоритма проста: всегда выбирайте активность, которая заканчивается раньше всех. Почему это работает? Представьте, что вы уже составили расписание из непересекающихся встреч, заканчивающихся как можно раньше. Если теперь рассмотреть следующую встречу, любая альтернатива, которая начинается позже, но заканчивается ещё позже, только сократит оставшееся время. Выбирая самую раннюю по окончанию активность, вы оставляете максимум места для остального расписания.

Доказательство основано на обменном аргументе: предположим, оптимальное решение отличается от жадного на первом шаге. Замените первую активность в оптимальном решении на жадную — так как она заканчивается не позже, остальное расписание остаётся выполнимым и не хуже по размеру. Повторяя замену, мы превращаем любое оптимальное решение в жадное без потери оптимальности.

Это «ага!» превращает кошмар экспоненциального перебора в линейный проход.

Реализация на Python: от брутфорса к жадному решению

Наивный подход (экспоненциальный)

Первая интуиция — отсортировать по времени начала и рекурсивно перебирать все совместимые следующие встречи:

def brute(intervals, i, last_end):
    if i == len(intervals):
        return 0
    # пропустить текущую
    best = brute(intervals, i + 1, last_end)
    # взять текущую, если совместима
    if intervals[i][0] >= last_end:
        best = max(best, 1 + brute(intervals, i + 1, intervals[i][1]))
    return best

Этот код работает за O(2^n) — для маленьких входов ещё терпимо, но быстро взрывается.

Жадный алгоритм (линейный после сортировки)

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

def activity_selection(starts, ends):
    # предполагается, что starts[i] < ends[i] и списки одинаковой длины
    intervals = sorted(zip(starts, ends), key=lambda x: x[1])  # сортировка по концу
    count = 0
    last_end = -float('inf')
    for s, e in intervals:
        if s >= last_end:  # совместима с уже выбранными
            count += 1
            last_end = e
    return count

Почему O(n): сортировка доминирует — O(n log n); сам проход — O(n). Если входные данные уже отсортированы по времени окончания (частый поворот на собеседованиях), алгоритм работает за чистый O(n).

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

Дано n встреч с временем начала и окончания. Найдите максимальное количество непересекающихся встреч, которые можно посетить. Просто передайте времена в activity_selection.

Вариация: задачи с дедлайнами

У вас есть список задач, каждая с длительностью и дедлайном. Максимизируйте количество задач, выполненных до дедлайна. Преобразуйте каждую задачу в интервал [start, start+duration], где start гибкий; жадное правило — «выбирай задачу с самым ранним дедлайном, которая помещается». Тот же проход после сортировки по дедлайну работает.

Типичные ошибки и как их избежать

• Сортировка по времени начала — кажется интуитивной, но приводит к выбору длинной встречи, блокирующей много коротких.
• Забыть обновить last_end — тогда вы будете считать пересекающиеся активности.
• Применять жадный алгоритм к взвешенным интервалам — доказательство ломается, когда у каждой активности есть вес; там нужно динамическое программирование.

Обнаружив эти ошибки на код-ревью, вы спасёте себя и коллегу от неприятного бага.

Почему этот навык важен для разработчика

Вооружившись жадным подходом, вы сможете решать целое семейство задач на интервалы, которые встречаются в проектировании систем (распределение ресурсов, планирование CPU, маршрутизация пакетов). Это также отличная тема для собеседования: вы можете объяснить обменный аргумент за минуту, показывая понимание не только «как», но и «почему».

Лучшее — паттерн повторяется. Как только вы увидите «самое раннее время окончания = оптимальный выбор», вы начнёте замечать похожие жадные возможности — например, выбор самой дешёвой монеты для размена (когда номиналы канонические) или выбор самой короткой задачи для минимизации времени ожидания. Каждый раз тот же обменный аргумент завершает доказательство.

Практический вывод: сделайте это прямо сейчас

Возьмите список встреч из своего календаря (или придумайте случайный набор) и вручную примените жадный алгоритм. Совпало ли количество с брутфорс-проверкой для маленького n? Попробуйте найти граничный случай, который пытается нарушить жадное правило. Удачного кодирования!