Слияние отсортированных интервалов после сортировки по левой границе
Реализуйте функцию merge_intervals(intervals).
Вход: intervals — список интервалов в произвольном порядке. Каждый интервал — список или кортеж из двух целых чисел [start, end], где всегда start <= end. Числа могут быть отрицательными и нулевыми.
Выход: новый список интервалов — результат объединения всех пересекающихся и соприкасающихся интервалов, отсортированный по возрастанию левой границы. Каждый интервал результата — список из двух чисел [start, end].
Правило соприкосновения: интервалы [1, 3] и [3, 5] считаются соприкасающимися и объединяются в [1, 5]. Интервалы [1, 3] и [4, 5] не объединяются.
Краевые случаи:
- пустой список: вернуть
[]; - один интервал: вернуть список с ним;
- вложенный интервал (
[1, 10]и[2, 3]) целиком поглощается: результат[[1, 10]].
Дополнительное требование: исходный список intervals изменять нельзя — ни его порядок, ни вложенные элементы. Результат всегда новый список списков.
заготовка решения
def merge_intervals(intervals):
# ваш код
pass