Объединение интервалов по условию ⇐ Python

[Anonymous]

Это классический подход к объединению интервалов:

Код: Выделить всё

def merge(intervals: List[List[int]]) -> List[List[int]]:
result = []
intervals.sort()
prev_interval = intervals[0]

for curr_interval in intervals[1:]:
if prev_interval[1] >= curr_interval[0]:  # Check if they overlap
prev_interval = [prev_interval[0], max(curr_interval[1], prev_interval[1])]
else:
result.append(prev_interval)
prev_interval = curr_interval

result.append(prev_interval)
return result

Я хотел бы изменить это решение, чтобы объединить интервалы, если «конец» любого интервала + 1 равен «началу» любого интервала в списке.

• Пример 1: интервалы = [[1,2], [3,4]] ==> [[1,4]]
• Пример 2: интервалы = [[1,5], [6,9]] ==> [[1,9]]
• Пример 3: интервалы = [ [1,5], [14, 17], [6,9], [10,13]] ==> [[1,17]]
• Пример 4: интервалы = [[1,5], [14, 17], [6,9], [10,13], [4,7], [8,12]] ==> [[1,17], [4 ,12]]

Я не могу опираться на свое текущее решение, поскольку не уверен, что интервалы, которые могут перекрываться, будут соседними в отсортированная форма списка заданных интервалов. Неэффективным решением было бы перебирать каждую комбинацию пар в списке и, если они перекрываются, удалять их из списка и помещать их объединение в результат.
Можете ли вы помочь мне создать это? функционировать наиболее оптимальным образом?

Подробнее здесь: https://stackoverflow.com/questions/790 ... -condition