合并两个有序无重叠区间列表的高效方法探讨

当然有更高效的方法！你提到的拼接后排序再合并的思路虽然直观，但因为两个输入列表A和B本身已经是无重叠且按起始点有序的，我们可以利用这个特性，用双指针法实现线性时间的合并，避免了排序带来的额外开销。

核心思路 #

既然两个列表都已按起始点排序，我们可以用两个指针分别遍历A和B，每次选择当前起始点更小的区间，然后和结果列表的最后一个区间对比，判断是否需要合并——这样全程只需要线性遍历，不需要对整个拼接后的列表排序。

具体步骤 #

1. 初始化两个指针 i = 0（指向A的第一个区间）、j = 0（指向B的第一个区间），同时创建一个空的结果列表 merged。
2. 当 i < len(A) 且 j < len(B) 时：
   • 比较 A[i][0] 和 B[j][0]，选择起始点更小的区间作为当前待处理区间。
   • 如果结果列表 merged 为空，直接将当前区间加入；否则，检查当前区间是否与 merged 的最后一个区间重叠：
     • 若重叠（当前区间的起始点 ≤ merged[-1][1]），则合并这两个区间：更新 merged[-1][1] 为两者结束点的最大值。
     • 若不重叠，直接将当前区间加入 merged。
   • 移动对应的指针（选了A的区间就 i += 1，选了B的区间就 j += 1）。
3. 处理剩余未遍历完的区间：
   • 如果A还有剩余区间，依次将每个区间与 merged 的最后一个区间对比，重叠则合并，否则直接加入。
   • 如果B还有剩余区间，执行同样的操作。

示例演示 #

假设：

• A = [[1, 3], [5, 7]]
• B = [[2, 4], [6, 8]]

执行流程：

1. i=0, j=0：A[0]起始1 < B[0]起始2，将[1,3]加入merged → merged = [[1,3]]，i变为1。
2. i=1, j=0：B[0]起始2 < A[1]起始5，检查[2,4]与[1,3]重叠，合并为[1,4] → merged = [[1,4]]，j变为1。
3. i=1, j=1：A[1]起始5 < B[1]起始6，[5,7]与[1,4]不重叠，加入merged → merged = [[1,4], [5,7]]，i变为2（A遍历完成）。
4. 处理B剩余的[6,8]：与merged最后一个[5,7]重叠，合并为[5,8] → merged = [[1,4], [5,8]]。

复杂度对比 #

• 双指针法：时间复杂度为 O(n + m)（n是A的长度，m是B的长度），仅需线性遍历两个列表；空间复杂度为 O(1)（除了存储结果的空间，不需要额外的排序空间）。
• 拼接排序法：时间复杂度为 O((n+m)log(n+m))，主要开销来自排序；空间复杂度取决于排序算法的实现（比如Python的sort用Timsort，空间复杂度O(n+m)）。

显然，当n和m较大时，双指针法的效率优势会非常明显。

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