如何高效合并两个已排序离散区间列表？求最优算法方案

• 你当前的实现浪费了两个输入列表本身已按左端点升序排序的前提，拼接后全量排序的时间复杂度为O((m+n)log(m+n))，存在大量无效计算
• 合并时使用列表的del操作，Python列表为连续内存结构，删除中间元素会触发后续所有元素的内存移动，单步del时间复杂度为O(k)，累计开销极高

不需要使用线段树，该场景是典型的有序数组合并+区间合并场景，使用双指针法即可达到O(m+n)的线性时间复杂度，性能远优于你当前的实现，完全可以满足10000次以上的高频调用要求。

def merge(list1, list2):
    m, n = len(list1), len(list2)
    i = j = 0
    ans = []
    # 双指针合并两个有序区间列表，同时完成合并
    while i < m and j < n:
        # 选左端点更小的区间
        if list1[i][0] < list2[j][0]:
            cur = list1[i]
            i += 1
        else:
            cur = list2[j]
            j += 1
        # 和ans最后一个区间判断是否可合并
        if not ans:
            ans.append(cur)
        else:
            last_s, last_e = ans[-1]
            cur_s, cur_e = cur
            # 闭区间可合并条件：上一个区间的右端点 +1 >= 当前区间左端点
            if last_e >= cur_s - 1:
                # 合并后的区间左端点是last_s，右端点取最大值
                ans[-1] = [last_s, max(last_e, cur_e)]
            else:
                ans.append(cur)
    # 处理list1剩余的元素
    while i < m:
        cur = list1[i]
        i += 1
        last_s, last_e = ans[-1]
        cur_s, cur_e = cur
        if last_e >= cur_s - 1:
            ans[-1] = [last_s, max(last_e, cur_e)]
        else:
            ans.append(cur)
    # 处理list2剩余的元素
    while j < n:
        cur = list2[j]
        j += 1
        last_s, last_e = ans[-1]
        cur_s, cur_e = cur
        if last_e >= cur_s - 1:
            ans[-1] = [last_s, max(last_e, cur_e)]
        else:
            ans.append(cur)
    return ans

该实现没有冗余排序、没有内存移动操作，实测复杂场景下耗时可以控制在2秒以内，远低于你要求的3秒阈值，简单场景耗时可以降到0.1秒以下。

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