如何在Python中高效合并元组列表中的重叠区间？

你的现有实现是正确的，而且已经是该问题的最优时间复杂度实现——合并区间问题的下界就是O(n log n)，因为必须先对区间按起始点排序，这一步的时间开销占主导，后续的线性遍历可以忽略不计。下面针对你的需求逐一说明：

一、性能优化建议 #

1. 利用有序输入：如果你的原始区间列表已经按start字段排序，可以直接跳过sorted()步骤，将时间复杂度降到O(n)，这是最大的性能提升点。
2. 减少不可变对象的创建：原代码中每次合并都要创建新元组(merged[-1][0], max(...))，可以改用列表存储中间结果（列表是可变类型），直接修改末尾区间的end值，最后再转回元组列表，能减少一些内存开销：

def merge_intervals(intervals):
    if not intervals:
        return []
    # 按起始点排序
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    merged = [list(sorted_intervals[0])]
    for curr_start, curr_end in sorted_intervals[1:]:
        last_interval = merged[-1]
        if curr_start > last_interval[1]:
            merged.append([curr_start, curr_end])
        else:
            # 仅当当前区间的end更大时才更新
            if curr_end > last_interval[1]:
                last_interval[1] = curr_end
    # 转回元组列表
    return [tuple(interval) for interval in merged]

二、更Pythonic的实现方式 #

可以用变量直接追踪前一个区间的起止点，避免频繁取merged[-1]，代码可读性更强：

def merge_intervals(intervals):
    if not intervals:
        return []
    # 按起始点排序
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    prev_start, prev_end = sorted_intervals[0]
    merged = []
    for curr_start, curr_end in sorted_intervals[1:]:
        if curr_start > prev_end:
            merged.append((prev_start, prev_end))
            prev_start, prev_end = curr_start, curr_end
        else:
            prev_end = max(prev_end, curr_end)
    # 加入最后一个合并后的区间
    merged.append((prev_start, prev_end))
    return merged

三、第三方库简化实现 #

Python标准库没有内置的合并区间函数，但可以用专门处理区间操作的第三方库intervaltree，它的实现经过优化，适合处理大规模数据：

1. 先安装库：

pip install intervaltree

2. 使用示例：

from intervaltree import IntervalTree

def merge_intervals(intervals):
    if not intervals:
        return []
    # 从元组列表构建区间树
    interval_tree = IntervalTree.from_tuples(intervals)
    # 合并重叠区间
    interval_tree.merge_overlaps()
    # 转换回排序后的元组列表
    return sorted((interval.begin, interval.end) for interval in interval_tree)

内容的提问来源于stack exchange，提问作者user23980631