Пересекающиеся интервалы на Python: задача с собеседования

Дана последовательность бронирований: каждое задаётся временем начала и окончания. Нужно узнать, сколько комнат понадобится в самый загруженный момент. В более общей форме мы ищем максимальное число одновременно активных интервалов.

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

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

Сначала уточните границы интервала

Пусть есть бронирования (10, 11) и (11, 12). Нужна одна комната или две? Ответ зависит от модели. Для бронирований обычно подходит полуинтервал [start, end): начало входит, окончание не входит. В 11:00 первая встреча уже закончилась, поэтому комнату можно сразу отдать второй.

Если предметная область считает обе границы включёнными, касание станет пересечением. На собеседовании это нельзя угадывать — правило нужно проговорить. Мы дальше используем полуинтервалы и считаем некорректным случай start >= end.

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

Решение через перебор временной шкалы

Прямой подход проходит по каждому целому моменту от минимального начала до максимального окончания. Для каждой точки он считает активные интервалы и запоминает максимум. Метод легко объяснить и отладить:

def max_overlap_bruteforce(intervals: list[tuple[int, int]]) -> int:
    # Для пустого списка одновременно не активно ни одного интервала.
    if not intervals:
        return 0

    left = min(start for start, _ in intervals)
    right = max(end for _, end in intervals)
    answer = 0

    for moment in range(left, right):
        # Полуинтервал активен, если start <= moment < end.
        active = sum(start <= moment < end for start, end in intervals)
        answer = max(answer, active)

    return answer

Проблема скрыта в диапазоне времени. При n интервалах и длине шкалы D получаем O(n · D). Если даты измеряются секундами на протяжении лет, D огромно, даже когда интервалов мало. Кроме того, такой вариант рассчитан на дискретное целое время.

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

Решение через события

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

Для n интервалов создаём 2n событий. Их сортировка требует O(n log n), проход — O(n), дополнительная память — O(n). Длина временной шкалы больше не влияет на скорость. Это классический подход sweep line, или «сканирующая прямая».

Коротко: метод событий сводит задачу к сортировке начал и окончаний и работает за O(n log n).

Напишите порядок событий прямо в коде

В Python кортежи сравниваются по элементам слева направо. Поэтому события (time, -1) и (time, +1) автоматически поставят окончание раньше начала при одинаковом времени. Это ровно то, что нужно для [start, end). Общие правила сортировки и сравнения ключей описаны в руководстве Python.

def max_overlap(intervals: list[tuple[int, int]]) -> int:
    events: list[tuple[int, int]] = []

    for start, end in intervals:
        # Пустые и обратные интервалы нарушают условие задачи.
        if start >= end:
            raise ValueError("start должен быть меньше end")
        events.append((start, 1))  # Один ресурс заняли.
        events.append((end, -1))   # Один ресурс освободили.

    # При одинаковом времени -1 идёт раньше +1:
    # завершившаяся встреча освобождает комнату для следующей.
    events.sort()

    active = 0
    answer = 0
    for _, delta in events:
        active += delta
        answer = max(answer, active)

    return answer

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

Проверьте решение на границах

Минимальный набор тестов раскрывает почти все ошибки:

• [] возвращает 0;
• [(1, 2)] возвращает 1;
• [(1, 2), (2, 3)] возвращает 1;
• [(1, 5), (2, 4), (3, 6)] возвращает 3;
• [(-3, -1), (-2, 2)] возвращает 2;
• интервал (4, 4) отклоняется.

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

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

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

Источники

• Python: приёмы и гарантии сортировки
• Python: сравнение последовательностей и других типов
• Тренажёр собеседований ЮНИКОД