← все задачи

Python · задача 5 из 10

Слить пересекающиеся интервалы

Средний 15–20 минут сортировкаинвариантыкраевые случаи

Условие

Дан список интервалов — например, занятых слотов календаря. Слейте пересекающиеся и верните минимальный набор непересекающихся интервалов, отсортированный по началу.

Что требуется

  • Интервалы приходят в произвольном порядке
  • Соприкасающиеся интервалы (конец одного равен началу другого) считаются смежными и сливаются
  • Пустой вход — пустой выход

Пример

merge([(1, 3), (2, 6), (8, 10), (15, 18)])
# [(1, 6), (8, 10), (15, 18)]

merge([(1, 4), (4, 5)])
# [(1, 5)]  -> соприкасаются, значит сливаем

Сначала уточните

Вопросы до кода — половина оценки. Молча начать печатать хуже, чем задать два вопроса.

  • Границы включительные или полуинтервал [start, end)? От этого зависит, сливать ли (1,4) и (4,5)
  • Может ли start быть больше end — данные заранее валидны?
  • Что на выходе: кортежи, списки, объекты? Нужен ли исходный список нетронутым?
Показать решение Скрыть решение

Решение

def merge(intervals):
    if not intervals:
        return []

    # сортируем по началу: после этого достаточно смотреть только на последний слитый
    ordered = sorted(intervals, key=lambda interval: interval[0])
    merged = [tuple(ordered[0])]

    for start, end in ordered[1:]:
        last_start, last_end = merged[-1]

        if start <= last_end:                      # пересекаются или соприкасаются
            merged[-1] = (last_start, max(last_end, end))
        else:
            merged.append((start, end))

    return merged

Почему так

Почему всё начинается с сортировки

  • После сортировки по началу возникает инвариант: новый интервал может пересечься только с последним слитым
  • Без него пришлось бы сравнивать каждый с каждым — O(n²) вместо O(n log n)
  • Проговорить инвариант вслух важнее, чем написать код: именно это интервьюер и слушает

Почему max(last_end, end)

  • Интервал может целиком лежать внутри предыдущего: (1, 10) и (2, 3) — конец брать нельзя, иначе результат сожмётся до (1, 3)
  • Это самый частый баг в этой задаче, и пример с вложенным интервалом обычно дают именно для проверки
  • Пример (1,10),(2,3) стоит проговорить самому до того, как его дадут

Почему start <= last_end, а не <

  • Строгое неравенство оставит (1,4) и (4,5) отдельными интервалами
  • Правильный ответ зависит от того, включительные границы или нет, — поэтому это первый вопрос интервьюеру
  • Любой вариант принимается, если вы объяснили выбор; молчаливое допущение — нет

Что спросят дальше

  • Спросят обратную задачу: найти свободные окна между занятыми слотами
  • Спросят про потоковый вариант: интервалы приходят по одному и уже отсортированы — тогда сортировка не нужна вовсе
  • В календарных задачах дальше идут часовые пояса — будьте готовы, что datetime с tz всплывёт

Следующая задача

Декоратор retry с экспоненциальной паузой — Самая частая задача на декораторы: проверяют и синтаксис, и понимание, что повторять можно не всё.

Перейти