在 Python 中合并重叠区间

Question

我正在尝试解决一个需要合并重叠间隔的问题。 问题是：

给定一个间隔集合，合并所有重叠的间隔。

例如，给定 [1,3],[2,6],[8,10],[15,18]，返回 [1,6],[8,10],[15,18]。

我尝试了我的解决方案：

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        start = sorted([x.start for x in intervals])
        end = sorted([x.end for x in intervals])
        
        merged = []
        j = 0
        new_start = 0
        
        for i in range(len(start)):
            if start[i]<end[j]:
                continue
            else:
                j = j + 1
                merged.append([start[new_start], end[j]])
                new_start = i
        
        return merged

然而，它显然缺少最后一个间隔：

Input : [[1,3],[2,6],[8,10],[15,18]]

Answer :[[1,6],[8,10]]

Expected answer: [[1,6],[8,10],[15,18]]

不确定如何包含最后一个间隔，因为只能在正向模式下检查重叠。

如何修复我的算法，使其一直有效到最后一个槽？

Answer 1

您的代码已隐式假设开始和结束已排序，因此可以省略该排序。要看到这一点，请尝试以下间隔：

intervals = [[3,9],[2,6],[8,10],[15,18]]
start = sorted([x[0] for x in intervals])
end = sorted([x[1] for x in intervals]) #mimicking your start/end lists
merged = []
j = 0
new_start = 0

for i in range(len(start)):
    if start[i]<end[j]:
        continue
    else:
        j = j + 1
        merged.append([start[new_start], end[j]])
        new_start = i
print(merged) #[[2, 9], [8, 10]]

不管怎样，最好的方法可能是递归，这里显示的是列表列表而不是Interval对象。

def recursive_merge(inter, start_index = 0):
    for i in range(start_index, len(inter) - 1):
        if inter[i][1] > inter[i+1][0]:
            new_start = inter[i][0]
            new_end = inter[i+1][1]
            inter[i] = [new_start, new_end]
            del inter[i+1]
            return recursive_merge(inter.copy(), start_index=i)
    return inter    

sorted_on_start = sorted(intervals)
merged = recursive_merge(sorted_on_start.copy())
print(merged) #[[2, 10], [15, 18]]