如何用Numpy实现区间去重：移除List1中与List2重叠的区间

需求说明 #

给定两个区间列表，需要移除List1中所有被List2覆盖的区间部分，保留未被覆盖的连续区间段。例如：

• List1：[(0,10),(15,20)]
• List2：[(2,3),(5,6)]
• 预期输出：[(0,2),(3,5),(6,10),(15,20)]

实现方案 #

下面是基于Numpy的实现代码，包含核心逻辑和优化处理：

1. 核心减法函数

import numpy as np

def subtract_intervals(list1, list2):
    result = []
    # 先合并List2中的重叠区间，提升处理效率
    list2_merged = merge_intervals(list2)
    
    for start1, end1 in list1:
        # 筛选出与当前List1区间有交集的List2区间
        overlaps = list2_merged[(list2_merged[:, 0] < end1) & (list2_merged[:, 1] > start1)]
        
        if len(overlaps) == 0:
            # 无重叠，直接保留原区间
            result.append((start1, end1))
            continue
        
        # 收集所有需要切割的端点：原区间首尾 + 所有重叠区间的端点
        points = np.concatenate([[start1], overlaps.flatten(), [end1]])
        # 排序并去重，确保端点按顺序排列
        points = np.unique(np.sort(points))
        
        # 遍历相邻端点，筛选未被覆盖的区间段
        for i in range(len(points) - 1):
            seg_start, seg_end = points[i], points[i+1]
            # 检查当前段是否被任意一个List2区间完全覆盖
            is_covered = False
            for s2, e2 in overlaps:
                if seg_start >= s2 and seg_end <= e2:
                    is_covered = True
                    break
            if not is_covered:
                result.append((seg_start, seg_end))
    
    return np.array(result)

2. 辅助函数：合并重叠区间

如果List2中存在重叠或相邻的区间，先合并它们可以减少后续的判断次数，提升效率：

def merge_intervals(intervals):
    if len(intervals) == 0:
        return np.array([])
    
    # 按区间起始点排序
    sorted_intervals = intervals[np.argsort(intervals[:, 0])]
    merged = [sorted_intervals[0]]
    
    for current in sorted_intervals[1:]:
        last_merged = merged[-1]
        # 当前区间与最后一个合并区间重叠，合并它们
        if current[0] <= last_merged[1]:
            merged[-1] = (last_merged[0], max(last_merged[1], current[1]))
        else:
            merged.append(current)
    
    return np.array(merged)

3. 测试示例

# 输入示例
list1 = np.array([(0, 10), (15, 20)])
list2 = np.array([(2, 3), (5, 6)])

# 执行减法
output = subtract_intervals(list1, list2)
print(output)

输出结果：

[[ 0  2]
 [ 3  5]
 [ 6 10]
 [15 20]]

关键逻辑说明 #

1. 重叠区间筛选：通过Numpy布尔索引快速找出与当前List1区间有交集的List2区间，避免遍历所有元素。
2. 端点切割：将原区间的首尾和所有重叠区间的端点合并排序，得到所有需要切割的位置，把原区间拆分成多个小段。
3. 有效段判断：对每个拆分后的小段，检查是否被List2的区间完全覆盖，未被覆盖的段就是需要保留的部分。

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