根据条件合并区间

Question

这是合并间隔的经典方法：

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]]

我无法在当前的解决方案之上构建，因为我不确定可能重叠的间隔在给定间隔列表的排序形式中是否相邻。一个低效的解决方案是迭代列表中的每对组合，如果它们重叠，则将它们从列表中删除并将它们的合并推入结果中。

你能帮我以尽可能最佳的方式创建这个功能吗？

Answer 1

您可以通过将间隔转换为字典来实现线性时间复杂度。从具有最小起点的范围开始，迭代地从 dict 中弹出起点，并测试该范围的终点加 1 是否作为 dict 中另一个范围的起点存在，并将其用作新的起点，直到不再有匹配的范围。找到，然后从最小开始的下一个范围开始，直到所有范围都被考虑在内：

def merge(intervals):
    result = []
    intervals = dict(intervals)
    while intervals:
        first = start = min(intervals)
        while (start := (end := intervals.pop(start)) + 1) in intervals:
            pass
        result.append([first, end])
    return result

这样：

print(merge([[1,5], [14, 17], [6,9], [10,13], [4,7], [8,12]]))

输出：

[[1, 17], [4, 12]]