如何在列表内部区间可重叠时高效查找两区间列表的交集

核心思路 #

由于原始双指针方法仅适用于内部无重叠的区间列表，针对内部有重叠的场景，我们可以先对两个列表分别合并重叠区间，同时记录每个合并区间对应的原始区间索引；再用经典双指针法找出合并后区间的重叠对；最后将合并区间对应的所有原始区间进行配对，得到所有符合要求的重叠区间对。这种方法的时间复杂度为O(n log n + m log m + k)（n、m为两列表长度，k为最终重叠对数），远优于暴力O(nm)解法。

具体步骤 #

1. 合并重叠区间并记录原始索引 #

对每个列表，先按区间左端点排序，再合并重叠/相邻区间，同时记录每个合并区间对应的原始区间索引列表。这样可以将内部重叠的区间转化为无重叠的合并区间，适配经典双指针法。

2. 双指针查找合并区间的重叠对 #

使用经典双指针法遍历两个合并后的无重叠区间列表，找出所有重叠的合并区间对。

3. 映射回原始区间对 #

对于每一对重叠的合并区间，将它们对应的所有原始区间进行两两配对，这些配对就是原始列表中所有的重叠区间对。

代码实现（Python） #

def merge_with_indices(intervals):
    # 为区间添加原始索引并按左端点排序
    indexed_intervals = sorted(
        [(interval[0], interval[1], idx) for idx, interval in enumerate(intervals)],
        key=lambda x: x[0]
    )
    if not indexed_intervals:
        return [], []
    
    merged = []
    indices_map = []
    current_s, current_e, current_indices = indexed_intervals[0][0], indexed_intervals[0][1], [indexed_intervals[0][2]]
    
    for s, e, idx in indexed_intervals[1:]:
        if s <= current_e:
            # 重叠则合并区间，追加原始索引
            current_e = max(current_e, e)
            current_indices.append(idx)
        else:
            # 不重叠则保存当前合并结果
            merged.append((current_s, current_e))
            indices_map.append(current_indices)
            current_s, current_e, current_indices = s, e, [idx]
    
    # 保存最后一组合并结果
    merged.append((current_s, current_e))
    indices_map.append(current_indices)
    return merged, indices_map

def find_merged_overlaps(merged_a, merged_b):
    i = j = 0
    overlaps = []
    while i < len(merged_a) and j < len(merged_b):
        a_s, a_e = merged_a[i]
        b_s, b_e = merged_b[j]
        
        if a_e < b_s:
            # a区间无法和b的后续区间重叠，移动a指针
            i += 1
        elif b_e < a_s:
            # b区间无法和a的后续区间重叠，移动b指针
            j += 1
        else:
            # 记录重叠的合并区间索引对
            overlaps.append((i, j))
            # 移动右端点较小的区间指针
            if a_e <= b_e:
                i += 1
            else:
                j += 1
    return overlaps

def find_all_overlap_pairs(A, B):
    # 合并区间并获取原始索引映射
    merged_a, idx_map_a = merge_with_indices(A)
    merged_b, idx_map_b = merge_with_indices(B)
    
    # 查找合并区间的重叠对
    merged_overlaps = find_merged_overlaps(merged_a, merged_b)
    
    # 生成所有原始区间重叠对
    result = []
    for a_merge_idx, b_merge_idx in merged_overlaps:
        a_original_indices = idx_map_a[a_merge_idx]
        b_original_indices = idx_map_b[b_merge_idx]
        # 两两配对原始区间
        for a_idx in a_original_indices:
            for b_idx in b_original_indices:
                # 若需要返回区间本身则用(A[a_idx], B[b_idx])，返回索引则用(a_idx, b_idx)
                result.append((A[a_idx], B[b_idx]))
    return result

正确性说明 #

• 合并后的区间是原始重叠区间的并集，若两个合并区间重叠，则它们对应的所有原始区间两两之间必然重叠；
• 反之，若原始列表中的两个区间重叠，则它们所属的合并区间必然重叠，不会遗漏任何有效配对。

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