如何用Numpy高效找出与所有其他区间均不相交的区间集合？

问题说明 #

我有一组约5万个元素的区间数据，想要找到与所有其他区间都不相交的区间集合，想问有没有高效且优雅的Numpy实现方式。我目前尝试的代码如下：

ranges = [[0,3], [2,4],[5,10]] # 实际约有5万个元素
disjoint_ranges = [] # 目标：所有互不相交的区间（原代码逻辑有误）
adjoint_ranges = [] # 记录有相交的区间
for index, range_1 in enumerate(ranges):
    i, j = range_1 # 所有区间满足i<j且已按i递增排序
    for swap_2 in ranges[index+1:]:
        a, b, _ = swap_2 # 此处会报错，原ranges仅含两个元素
        if a<j and a>i:
            adjoint_swaps.append(swap) # swap未定义
            adjoint_swaps.append(swap_2)
    else:
        if swap not in adjoint_swaps: # swap未定义
            swaps_to_do.append(swap)
print(adjoint_swaps)
print(swaps_to_do)

原代码问题 #

1. 变量错误：swap、adjoint_swaps、swaps_to_do未定义，swap_2拆包时多写_导致报错
2. 效率极低：双重Python循环时间复杂度为O(n²)，处理5万条数据会极慢，甚至无法完成计算

高效Numpy实现方案（利用区间已排序特性） #

已知你的区间已按起始点升序排列，我们可以利用这个特性做线性时间优化，避免两两比较：

核心思路

对于每个区间，只需同时满足两个条件：

1. 它的起始点大于等于前面所有区间的最大结束点（确保和前面所有区间不相交）
2. 它的结束点小于等于后面所有区间的最小起始点（确保和后面所有区间不相交）

代码实现

import numpy as np

# 替换为你的5万条区间数据（已按起始点升序排列）
ranges = np.array([[0,3], [2,4], [5,10], [11,15]])

starts = ranges[:, 0]
ends = ranges[:, 1]
n = len(ranges)

# 计算前缀结束点最大值：prefix_max_end[i] 是前i个区间（0到i-1）的结束点最大值
prefix_max_end = np.zeros(n, dtype=np.int64)
prefix_max_end[0] = -np.inf  # 第一个区间前面没有区间
for i in range(1, n):
    prefix_max_end[i] = max(prefix_max_end[i-1], ends[i-1])

# 计算后缀起始点最小值：suffix_min_start[i] 是i+1到末尾区间的起始点最小值
suffix_min_start = np.zeros(n, dtype=np.int64)
suffix_min_start[-1] = np.inf  # 最后一个区间后面没有区间
for i in range(n-2, -1, -1):
    suffix_min_start[i] = min(suffix_min_start[i+1], starts[i+1])

# 筛选出与所有其他区间都不相交的区间
is_disjoint = (prefix_max_end <= starts) & (suffix_min_start >= ends)
disjoint_ranges = ranges[is_disjoint]

print(disjoint_ranges)
# 输出结果：
# [[ 5 10]
#  [11 15]]

方案优势

• 时间复杂度O(n)，内存复杂度O(n)，处理5万条数据毫无压力
• 基于Numpy数组操作，避免了低效的Python循环
• 利用区间排序特性，大幅减少计算量

通用版实现（区间未排序的情况） #

如果你的区间未排序，可以先排序再用上面的方案；也可以用Numpy广播实现两两比较（注意：5万条数据会生成5万×5万的矩阵，占用约2.5GB内存，需确保内存足够）：

import numpy as np

ranges = np.array([[0,3], [2,4], [5,10], [11,15]])
n = ranges.shape[0]

starts = ranges[:, 0]
ends = ranges[:, 1]

# 广播计算所有区间对的相交情况：intersects[i,j]表示区间i和j是否相交
intersects = (starts[:, None] < ends) & (starts < ends[:, None])
# 排除区间与自身相交的情况
np.fill_diagonal(intersects, False)

# 筛选出与所有其他区间都不相交的区间（对应行无True值）
is_disjoint = ~intersects.any(axis=1)
disjoint_ranges = ranges[is_disjoint]

print(disjoint_ranges)

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