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

Вы когда-нибудь пытались втиснуть максимум встреч в свой календарь? Наивный подход — брать самую раннюю встречу, затем следующую непересекающуюся — часто оставляет пробелы, где можно было бы провести ещё одну. Эта задача известна как выбор активности (activity selection), и решается она элегантным жадным алгоритмом, который вы сможете применить и на собеседовании, и в реальных проектах.

Суть жадного подхода: сортировка по времени окончания

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

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

Код: от перебора к жадности

Сначала покажу медленный перебор (экспоненциальная сложность), затем жадное решение.

def max_meetings_brute(intervals):
    # intervals = [(start, end), ...]
    from functools import lru_cache
    intervals.sort()  # по start, для определённости
    n = len(intervals)

    @lru_cache(None)
    def dfs(i, last_end):
        if i == n:
            return 0
        # пропустить текущий
        best = dfs(i + 1, last_end)
        # взять текущий, если не пересекается
        s, e = intervals[i]
        if s >= last_end:
            best = max(best, 1 + dfs(i + 1, e))
        return best

    return dfs(0, -float('inf'))

Для 20 интервалов это уже миллионы вызовов — не годится для интервью.

А вот жадное решение:

def max_meetings_greedy(intervals):
    # intervals = [(start, end), ...]
    # 1️⃣ Сортируем по времени окончания (ключ жадности)
    intervals.sort(key=lambda x: x[1])  # O(n log n)
    count = 0
    last_end = -float('inf')
    for s, e in intervals:  # ❶ O(n) проход
        if s >= last_end:   # можем ли мы посетить?
            count += 1
            last_end = e   # фиксируем конец
    return count

Сложность O(n log n) из-за сортировки, сам проход — O(n).

Частые ошибки новичков

Сортировка по времени начала — интуитивно, но провально: длинная встреча, начинающаяся рано, блокирует много коротких.
Забыть обновить last_end — тогда пересекающиеся интервалы будут считаться как последовательные.
Использовать < вместо >= — пропустите интервалы, начинающиеся ровно в момент окончания предыдущего (они допустимы).

Разбор задач с LeetCode

LeetCode 435: Non-overlapping Intervals

Удалить минимум интервалов, чтобы остальные не пересекались. Ответ: общее количество − max_meetings_greedy(intervals). Ведь максимум непересекающихся эквивалентен минимуму удалений.

LeetCode 253: Meeting Rooms II

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

Почему это важно за пределами собеседований

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

Однажды на работе мы планировали задания для пайплайнов данных с разной длительностью и дедлайнами. Отсортировав по времени последнего возможного старта (аналог времени окончания) и жадно выбирая, мы сократили задержку пайплайна на 30%. Команда была в восторге.

Ваше задание

Попробуйте: дан список лекций в аудиториях (время начала и конца). Напишите функцию, которая возвращает максимум лекций, которые можно посетить без перехода между аудиториями (вы остаётесь в одной). Подумайте, как меняется жадный подход при наличии нескольких одинаковых ресурсов. Оставьте решение в комментариях или объясните, почему жадность по раннему окончанию работает для каждой аудитории отдельно, и где нужна модификация.

Пусть ваши интервалы будут короткими, а расписания — жадными! 🚀

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