如何求两个有序区间数组的交集？最优算法探讨

嘿，这个问题我太熟了——这是经典的已排序区间数组求交集场景，暴力两两匹配确实低效得离谱，最优解肯定是用双指针法，刚好能利用两个数组已经排序的特性，把时间复杂度压到线性级别。

核心思路 #

既然两个区间数组都是按起始值升序排列的，我们可以用两个指针分别遍历A和B，全程不需要回头：

• 初始化指针i（指向A的起始）和j（指向B的起始）
• 循环直到其中一个指针越界：
  1. 计算当前两个区间的交集范围：交集的起始是两个区间起始值的最大值，结束是两个区间结束值的最小值
  2. 如果起始值 ≤ 结束值，说明这是一个有效交集，把它加入结果数组
  3. 移动结束值更小的那个区间的指针——因为这个区间已经不可能再和另一个数组的后续区间产生交集了，直接推进到下一个区间即可

代码实现（Python示例） #

def interval_intersection(A, B):
    i = j = 0
    result = []
    while i < len(A) and j < len(B):
        a_start, a_end = A[i]
        b_start, b_end = B[j]
        # 计算交集的起止边界
        intersect_start = max(a_start, b_start)
        intersect_end = min(a_end, b_end)
        # 判断是否为有效交集
        if intersect_start <= intersect_end:
            result.append([intersect_start, intersect_end])
        # 移动指针：结束值小的区间先推进
        if a_end < b_end:
            i += 1
        else:
            j += 1
    return result

# 测试题目中的示例
A = [[1, 3], [7, 9], [12, 18]]
B = [[2, 3], [4,5], [6,8], [13, 14], [16, 17]]
print(interval_intersection(A, B))  # 输出: [[2, 3], [7, 8], [13, 14], [16, 17]]

为什么这是最优解？ #

• 时间复杂度：每个指针最多遍历各自数组一次，总遍历次数是n+m，因此时间复杂度为O(n+m)，比暴力法的O(n*m)高效几个量级，尤其当数组规模较大时优势明显
• 空间复杂度：除了存储结果的数组外，只用到了两个指针变量，空间复杂度为O(1)（不计结果存储的话）

内容的提问来源于stack exchange，提问作者Ionică Bizău