Слияние пересекающихся интервалов
Объединяйте соприкасающиеся или пересекающиеся диапазоны
«Слияние пересекающихся интервалов» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Цель объединения
Для заданного набора интервалов требуется объединить соприкасающиеся или пересекающиеся интервалы в минимальное число непересекающихся диапазонов. 🧩
Когда два интервала пересекаются
Два интервала пересекаются, если один начинается до того, как другой заканчивается. После сортировки по началу это означает, что следующее начало не превышает текущий конец.
Всегда начинайте с сортировки
Объединять интервалы слева направо можно только в правильном порядке, поэтому начните с их сортировки по началу. Это основа всего прохода.
intervals.sort(key=lambda x: x[0])Храните текущий диапазон
Проходите отсортированный список, сохраняя один текущий объединённый интервал. Каждый новый интервал либо расширяет его, либо начинает новый диапазон.
Расширяйте при пересечении
Если следующее начало находится внутри текущего диапазона, интервалы пересекаются, поэтому увеличьте текущий конец до большего из двух концов.
cur_end = max(cur_end, end)Берите максимальный конец
Для нового конца всегда используйте максимум. Короткий интервал, вложенный в длинный, не должен уменьшать уже построенный диапазон.
Закройте текущий и откройте новый
Если следующее начало находится за текущим концом, между интервалами есть разрыв. Добавьте завершённый диапазон в ответ и начните новый текущий интервал.
result.append([cur_start, cur_end])Не забудьте последний
Цикл строит последний диапазон, но не добавляет его в ответ. После завершения цикла append последний текущий интервал, чтобы он не потерялся.
Соприкосновение считается пересечением
Определите, следует ли объединить [1, 3] и [3, 5]. Обычно следует, поэтому используйте start <= cur_end. Прочитайте условие задачи, чтобы подтвердить это правило для граничного случая.
Полный проход
Один проход после сортировки даёт все объединённые диапазоны, поэтому весь метод работает за O(n log n): сортировка выполняется за логарифмическое время, а проход — за линейное.
for s, e in intervals[1:]:
if s <= cur_end:
cur_end = max(cur_end, e)
else:
result.append([cur_start, cur_end]); cur_start, cur_end = s, eРаспространённое применение
Объединение интервалов лежит в основе календарей и систем бронирования: объединяйте занятые блоки, чтобы увидеть настоящее свободное время. Во многих задачах соревнований встречается эта же структура.
Быстрая проверка
Вы объединяете интервалы после сортировки по началу.
Итоги
Сортируйте по началу, храните текущий диапазон и расширяйте его с помощью max при пересечении либо добавляйте и начинайте заново при разрыве. Не забудьте о последнем append. 🚀
Часто задаваемые вопросы
Урок «Слияние пересекающихся интервалов» бесплатный?
Да — полный текст урока «Слияние пересекающихся интервалов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Слияние пересекающихся интервалов»?
Объединяйте соприкасающиеся или пересекающиеся диапазоны Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Слияние пересекающихся интервалов»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Сортировка интервалов по началу
- Слияние пересекающихся интервалов
- Метод сканирующей прямой для максимального перекрытия
- Минимальное число удалений без перекрытий