Войти Регистрация
Алгоритмы

22. Слияние отрезков

Средняя

Дан список отрезков segs, каждый — [начало, конец], начало ≤ конца, в любом порядке. Объедините пересекающиеся и касающиеся отрезки ([1, 2] и [2, 3] дают [1, 3]).

Верните результат по возрастанию начала.

В работе: Склеить занятые интервалы в календаре переговорки.

Пример 1

Ввод
segs = [[5, 8], [1, 2], [7, 10], [2, 3]]
Вывод
[[1, 3], [5, 10]]

Пример 2

Ввод
segs = [[4, 6]]
Вывод
[[4, 6]]

Ограничения

  • 0 ≤ число отрезков ≤ 10⁵
  • −10⁹ ≤ концы ≤ 10⁹
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def merge_intervals(segs):
СортировкаИнтервалыцельO(n log n)

Источник: отчёт о Яндексе, 2021. Условие пересказано своими словами.

Ещё давали: тег Ozon на LeetCode; Сбер, каталог задач solvit.space.

Давали на собеседовании? Ответов пока мало — ваш поможет.