# Авторская практика объединения интервалов

Это не реальное задание работодателя. Для запуска нужен Python3.9+ без пакетов: `python3 verify.py`.

## Учебная задача: объединить интервалы доступности

Это оригинальная задача для подготовки к объяснению алгоритма. Она не является реальным вопросом Google.

Условие: получен список интервалов доступности одного ресурса в пределах одного условного дня. Границы — целые минуты от начала дня: `0 ≤ start < end ≤ 1440`. Интервал полуоткрытый: `[start, end)`. Нужно вернуть отсортированные непересекающиеся интервалы, представляющие ту же доступность. По договорённости соприкасающиеся интервалы тоже объединяются. Исходный список менять нельзя. Повторы допустимы; некорректный интервал должен вызвать ошибку, а не исчезнуть молча.

Вход: `[(600, 660), (540, 600), (570, 630), (720, 750), (600, 660)]`.

Ожидаемый ответ: `[(540, 660), (720, 750)]`. Первые три разных интервала вместе покрывают время с 09:00 до 11:00. Повтор не создаёт дополнительной доступности. От 11:00 до 12:00 ресурса в этой модели нет; второй участок начинается в 12:00 и заканчивается в 12:30.

Это задача об объединении доступности одного ресурса. Она не ищет общие окна нескольких участников, не учитывает уже занятые встречи и не бронирует календарь. Если поменять вопрос на «когда свободны все трое», понадобится другой алгоритм и данные о каждом участнике.

## Уточнения и пример решения вручную

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

После сортировки по началу получаем `(540, 600)`, `(570, 630)`, два раза `(600, 660)`, затем `(720, 750)`. Начинаем с первого участка. Следующий начинается раньше его конца, поэтому расширяем конец до 630. Следующий расширяет до 660. Его повтор уже целиком покрыт и ничего не меняет. Последний начинается после 660: предыдущий участок закончен, открывается новый.

Проверка соприкосновения отдельная: `[(10, 20), (20, 30)]` превращается в `[(10, 30)]`. Мы не утверждаем, что исходные полуоткрытые интервалы имеют общий момент; по правилу задачи их объединение представляет один непрерывный участок. Для другой бизнес-задачи это правило может отличаться.

## Алгоритм и доказательство

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

```python
def merge_availability(intervals):
    source = list(intervals)
    for item in source:
        if not isinstance(item, (tuple, list)) or len(item) != 2:
            raise ValueError("Expected a pair")
        start, end = item
        if type(start) is not int or type(end) is not int:
            raise ValueError("Expected integer minutes")
        if not 0 <= start < end <= 1440:
            raise ValueError("Invalid interval")
    merged = []
    for start, end in sorted(source, key=lambda pair: (pair[0], pair[1])):
        if merged and start <= merged[-1][1]:
            merged[-1] = (merged[-1][0], max(merged[-1][1], end))
        else:
            merged.append((start, end))
    return merged
```

[Документация Python](https://docs.python.org/3/howto/sorting.html) различает изменяющий список `list.sort()` и создающий новый список `sorted()`. Здесь нужен второй вариант: условие запрещает менять исходник. Функция дополнительно материализует вход, чтобы проверка и сортировка работали с одной сохранённой последовательностью.

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

Сортировка даёт оценку времени `O(n log n)` для общего несортированного входа, проход — `O(n)`. Сохранённый вход и результат требуют `O(n)` дополнительной памяти в худшем случае. Если вход уже отсортирован и это гарантирует контракт, возможен линейный вариант; в нашем условии такой гарантии нет.

## Проверки и границы задачи

В приложении есть восемь проверок: основной пример; пустой ввод; вложение; соприкосновение; границы дня; сохранение исходника; несколько видов недопустимых значений; сравнение покрытия на небольших наборах. Последняя сверяет минуты исходного и объединённого результата, а не только повторяет условие `if` из реализации.

Запуск: из папки `interval-practice` выполни `python3 verify.py`. Сторонних пакетов нет. Используется Python 3.9 или новее. Успешный прогон относится к этим условиям и входному контракту; он не проверяет любой календарный сервис.

Реальное время требует отдельной постановки. Дата, смещение относительно UTC и переходы местного времени не представлены простым числом минут. [RFC 3339](https://www.rfc-editor.org/rfc/rfc3339) описывает временные отметки с отношением к UTC, но не задаёт алгоритм объединения интервалов. Поэтому нельзя назвать эту функцию готовой поддержкой международных календарей, просто заменив числа строками времени.

Если интервьюер добавит новое условие, сначала пересмотри модель: разные ресурсы требуют раздельной группировки; сохранение всех источников — дополнительного набора идентификаторов; очень большой поток — иного способа хранения и сортировки. Не исправляй только пример ответа, оставив старую формулировку задачи.

