面试题：求两个有序无重叠区间列表的重叠区间

嘿，我完全懂这种面试卡壳的感觉！这种有序区间的重叠问题其实用双指针就能轻松搞定，咱们一步步来拆解清楚。

核心思路 #

因为A和B都是按起始点排序且内部无重叠的区间列表，所以根本不需要暴力遍历所有区间组合。我们可以用两个指针分别遍历A和B，每次只对比当前指向的两个区间，判断是否重叠，然后根据区间的结束点决定移动哪个指针——哪个区间结束得更早，就移动对应的指针，因为它不可能再和另一个列表的后续区间产生重叠了（毕竟后续区间的起始点只会更大）。

重叠判断规则 #

对于两个区间 [a1, a2]（来自A）和 [b1, b2]（来自B）：

• 它们的重叠区间起始点是两个区间起始点的最大值：max(a1, b1)
• 重叠区间结束点是两个区间结束点的最小值：min(a2, b2)
• 如果 max(a1, b1) <= min(a2, b2)，说明两个区间有重叠，把这个重叠区间加入结果列表。

示例走一遍 #

拿你给出的例子来实际推演：

• A: [[0,4], [7,12]]，B: [[1,3], [5,8], [9,11]]
• 初始指针i=0（指向A的第一个区间），j=0（指向B的第一个区间）

1. 对比[0,4]和[1,3]：max(0,1)=1，min(4,3)=3，1<=3，所以重叠区间[1,3]加入结果。因为4>3，B的当前区间结束更早，j++到1。
2. 对比[0,4]和[5,8]：max(0,5)=5，min(4,8)=4，5>4，无重叠。因为4<8，A的当前区间结束更早，i++到1。
3. 对比[7,12]和[5,8]：max(7,5)=7，min(12,8)=8，7<=8，重叠区间[7,8]加入结果。因为12>8，B的当前区间结束更早，j++到2。
4. 对比[7,12]和[9,11]：max(7,9)=9，min(12,11)=11，9<=11，重叠区间[9,11]加入结果。因为12>11，j++到3，超出B的长度，循环结束。
   最终结果就是[[1,3], [7,8], [9,11]]，和示例完全一致。

代码实现（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]
        
        # 计算可能的重叠区间
        overlap_start = max(a_start, b_start)
        overlap_end = min(a_end, b_end)
        
        # 判断是否真的重叠
        if overlap_start <= overlap_end:
            result.append([overlap_start, overlap_end])
        
        # 移动结束更早的区间指针
        if a_end < b_end:
            i += 1
        else:
            j += 1
    return result

关键点说明 #

• 时间复杂度：O(m + n)，其中m和n分别是A和B的区间数量，每个区间最多被访问一次，是最优解法。
• 边界情况：如果其中一个列表为空，直接返回空列表；如果区间首尾相接（比如[2,5]和[5,7]），代码会把[5,5]算作重叠区间，符合闭区间的重叠定义。

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