求助：Python中高效识别列表中非重叠区间的方法

嵌套循环O(n²)的效率确实拉胯，大数据量下完全没法用。给你推荐两种核心思路，还有现成的库可以用：

排序+线性遍历（手动实现，O(n log n)效率） #

这是最经典的解法，排序后线性遍历就行，时间主要花在排序上，比嵌套循环快太多。

场景1：找最大的非重叠区间子集 #

就是选出最多的不重叠区间，步骤如下：

1. 把所有区间按终点升序排序（按终点排比起点排更方便判断）
2. 从第一个区间开始，依次往后找，只要当前区间的起点 >= 上一个选中区间的终点，就把它加入结果列表

代码示例：

intervals = [(1, 3), (2, 4), (5, 7), (6, 8)]
# 按区间终点排序
sorted_intervals = sorted(intervals, key=lambda x: x[1])

non_overlapping = []
if sorted_intervals:
    non_overlapping.append(sorted_intervals[0])
    for current in sorted_intervals[1:]:
        last_selected = non_overlapping[-1]
        if current[0] >= last_selected[1]:
            non_overlapping.append(current)

print(non_overlapping)  # 输出: [(1, 3), (5, 7)]

场景2：找完全不与任何其他区间重叠的区间 #

如果你的需求是找出那些完全没交集的区间（既不跟别的区间重叠，也不包含/被包含），可以这么做：

1. 先按起点排序
2. 从左到右遍历，标记每个区间是否被左边的区间重叠
3. 再从右到左遍历，标记每个区间是否被右边的区间重叠
4. 最后筛选出两次标记都为“无重叠”的区间

代码示例：

intervals = [(1, 3), (2, 4), (5, 7), (8, 10)]
sorted_by_start = sorted(intervals, key=lambda x: x[0])
n = len(sorted_by_start)

# 标记是否被左边区间重叠
left_overlap = [False] * n
max_end = sorted_by_start[0][1]
for i in range(1, n):
    if sorted_by_start[i][0] < max_end:
        left_overlap[i] = True
    max_end = max(max_end, sorted_by_start[i][1])

# 标记是否被右边区间重叠
right_overlap = [False] * n
min_start = sorted_by_start[-1][0]
for i in range(n-2, -1, -1):
    if sorted_by_start[i][1] > min_start:
        right_overlap[i] = True
    min_start = min(min_start, sorted_by_start[i][0])

# 筛选完全不重叠的区间
result = [sorted_by_start[i] for i in range(n) if not left_overlap[i] and not right_overlap[i]]
print(result)  # 输出: [(5, 7), (8, 10)]

现成Python库推荐 #

不想自己写逻辑的话，用这些库能省事儿：

• pandas：用DataFrame的排序和移位功能快速筛选
  代码示例：

  import pandas as pd
  df = pd.DataFrame(intervals, columns=['start', 'end'])
  df = df.sort_values('end')
  # 用上一个区间的终点和当前区间起点比较
  df['last_end'] = df['end'].shift(1).fillna(-float('inf'))
  non_overlapping_df = df[df['start'] >= df['last_end']]
  print(non_overlapping_df.values.tolist())
  

• intervaltree：专门处理区间的库，支持快速查询重叠情况
  先安装：pip install intervaltree
  代码示例：

  from intervaltree import IntervalTree
  tree = IntervalTree.from_tuples(intervals)
  non_overlapping = []
  for interval in intervals:
      # 查询当前区间的所有重叠区间，排除自身
      overlaps = tree.search(interval[0], interval[1])
      if len(overlaps) == 1 and overlaps.pop() == interval:
          non_overlapping.append(interval)
  print(non_overlapping)
  

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