Python интервалы слияния списков

Question

Я начал практиковать вопросы по leetcode и, будучи новичком, столкнулся с некоторыми незначительными проблемами с этим подходом. Задача состоит в том, чтобы объединить все перекрывающиеся интервалы. *

Вот что я пробовал:

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 1:
            return intervals
        intervals = sorted(intervals)
        i = 0
        k = 0
        while i < len(intervals)-1:
            k = k + 1
            for j in range(i+1,len(intervals)):                
                if intervals[i][1] >= intervals[j][0]:
                    intervals[i] = [intervals[i][0],max(intervals[i][1],intervals[j][1])]
                    del intervals[j]
                    i = i + 1
                else:
                    intervals[i] = [intervals[j-1][0],intervals[j-1][1]]
                    i = j
                    break       

            print(intervals,k)            
        return intervals[:k+1]

Я считаю, что точка, в которой я борюсь, - это оператор else, в котором я обновляю список, если не найдено перекрывающихся интервалов. Любая помощь в указании того, где я ошибаюсь, была бы замечательной.

Ссылка на проблему, если требуется: Интервалы слияния

Answer 1

Одна проблема:

del intervals[j]

Изменение контейнера во время итерации по нему, как правило, плохая идея. Это часто приводит к пропуску или дублированию значений.

Рассмотрим внутренний l oop, когда i=0 и j=1:

  i=0   j=1 
[[1,3],[2,6],[8,10],[15,18]]

Интервалы перекрываются, поэтому выполняется блок if:

intervals[i] = [intervals[i][0],max(intervals[i][1],intervals[j][1])]

, в результате получается:

  i=0   j=1 
[[1,6],[2,6],[8,10],[15,18]]

затем

del intervals[j]

в результате:

  i=0   j=1 
[[1,6],[8,10],[15,18]]

затем:

i = i + 1

в результате:

        i=j=1 
[[1,6],[8,10],[15,18]]

Но теперь for-l oop увеличивает j:

        i=1     j=2 
[[1,6],[8,10],[15,18]]

Обратите внимание, как j пропускает интервал [8,10]?

Лучше создать новый список интервалов слияния. Если вам необходимо сделать это на месте, работайте в обратном направлении от конца списка. Таким образом, любые измененные индексы будут уже обработанными.