Ошибка в условии слияния: код проверяет $res[-1][1]<b$ (сравнивает конец предыдущего интервала с концом текущего), а нужно сравнивать с началом текущего интервала. Правильное условие — неналожение, когда конец предыдущего < начало текущего: $res[-1][1]<a$.
Пример, где оригинал даёт неверный результат:
- Вход: $[[1,3],[2,4]]$.
- Ожидаемый результат: $[[1,4]]$.
- Оригинал (с $res[-1][1]<b$) добавит второй интервал отдельно, т.к. $3<4$ — неверно.
Исправленный код:
def merge(intervals):
intervals.sort(key=lambda x: x[0])
res = []
for a, b in intervals:
if not res or res[-1][1] < a:
res.append([a, b])
else:
res[-1][1] = max(res[-1][1], b)
return res
Комментарии:
- Явная сортировка по началу интервала безопаснее: $.sort(key=lambdax:x[0])$.
- Следует использовать Python-ключевое слово `return`.
Сложность:
- Временная: $O(n\log n)$ (сортировка) + $O(n)$ проход → в сумме $O(n\log n)$.
- Пространственная: дополнительный результат до $O(n)$. Если не считать выходные данные, дополнительная память $O(\log n)$ для сортировки (в зависимости от реализации).