Задача с собеседования в Zalando

Дан массив интервалов, где intervals[i] = [starti, endi]. Необходимо объединить все пересекающиеся интервалы, а затем вернуть массив, состоящий из непересекающихся интервалов, которые покрывают все интервалы из входных данных.

Пример 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Пример 2:
Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]

Чат алгоритмистов

Решение
1. Сортируем интервалы по началу, это гарантирует: если текущий интервал не пересекается с последним, то он не может пересекаться с каким-либо более ранним, т.к. все предыдущие интервалы имеют начало не больше, чем у последнего, и если последний заканчивается до начала текущего, то все предыдущие тем более закончились раньше. Это позволяет решить задачу за один проход.

2. Проходим по каждому отсортированному интервалу в массиве:

- добавляем новый интервал в список, если это первый интервал в списке ИЛИ если конец последнего интервала меньше начала текущего
(в merged лежит [1,6], а текущий интервал [8,10], 6 < 8 => интервалы не пересекаются => добавляем [8,10] как новый интервал).

- иначе объединяем его с последним интервалом и обновляем конец
(в merged лежит [1,3], текущий интервал = [2,6], они пересекающиеся, так как 3 ≥ 2. Обновляем конец объединённого интервала: max(3, 6) = 6, то есть [1,6]).

Сложность
O(n log n) - по времени
O(n) - по памяти

Код

class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda interval: interval[0])
merged = []

for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])

return merged

@algoses