Дан список интервалов [start, end]. Объедините все пересекающиеся интервалы и верните результат без пересечений.
Короткий ответ
- Без сортировки пересечения разбросаны — сначала сортируем по началу
- После сортировки пересекаться могут только соседние интервалы
- Идём по списку, сравнивая start с концом последнего в результате
- Пересечение: новый конец — максимум двух концов
- Нет пересечения: интервал просто добавляется
- Касание границ обычно считается пересечением — уточнить
- Сортировка доминирует: O(n log n)
Сортировка по началу и один жадный проход со слиянием соседей решают задачу за O(n log n) времени и O(n) памяти на результат.
Как сказать вслух
пример ответаСначала я отсортирую интервалы по левой границе — после этого любые пересечения оказываются между соседями. Дальше один проход: если текущий интервал начинается не позже конца последнего собранного, сливаю их, беря максимум концов. Максимум важен, потому что интервал может целиком лежать внутри предыдущего.
Подробный ответ
Основной ответ
Сортируем интервалы по start — это ключевая редукция: теперь если текущий интервал не пересекается с последним собранным, то не пересечётся и ни с каким последующим. Проход: берём первый интервал в результат; для каждого следующего сравниваем его start с end последнего интервала результата. Если start <= end — пересечение или касание: обновляем конец последнего интервала как max(прежний end, текущий end). Максимум обязателен из-за вложенных интервалов: [1, 10] и [2, 3] должны дать [1, 10], а не [1, 3]. Иначе интервал добавляется как новый. Время O(n log n) из-за сортировки, сам проход линеен; память O(n) под результат (или O(log n), если сортировка на месте и результат не считать). Границу «касание [1,2] и [2,3]» стоит проговорить: обычно сливают, тогда условие start <= end.
Ключевые моменты
- Зачем сортировка. Упорядоченность по началу гарантирует, что все пересечения — между соседями, и задача решается одним проходом.
- Максимум концов. Вложенный интервал короче объемлющего; без max результат ошибочно сужается.
- Условие слияния. start <= end сливает касающиеся интервалы; строгое < оставляет их раздельными — согласуйте с интервьюером.
- Сложность. O(n log n) времени за счёт сортировки, проход O(n); быстрее нельзя без предположений о входе.
Практический контекст
Интервальные задачи — большое семейство: вставка интервала в отсортированный список, минимум переговорок (meeting rooms), пересечение двух списков интервалов. Интервьюер проверяет, догадаетесь ли вы до сортировки и не споткнётесь ли на вложенных интервалах. Уточните: отсортирован ли вход заранее, сливать ли касающиеся границы, могут ли интервалы быть некорректными (start > end).
Пример кода
def merge_intervals(intervals):
intervals.sort(key=lambda p: p[0])
res = []
for start, end in intervals:
if res and start <= res[-1][1]: # пересечение или касание
res[-1][1] = max(res[-1][1], end) # max: интервал может быть вложен
else:
res.append([start, end])
return res
assert merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]) == [[1, 6], [8, 10], [15, 18]]
assert merge_intervals([[1, 10], [2, 3]]) == [[1, 10]]
assert merge_intervals([[1, 2], [2, 3]]) == [[1, 3]]
assert merge_intervals([]) == []Частые ошибки
- Пытаются сливать без предварительной сортировки и пропускают непоследовательные пересечения
- Присваивают концу текущее значение вместо максимума — вложенные интервалы обрезают результат
- Не уточняют, считается ли касание границ ([1,2] и [2,3]) пересечением