如何在Python中删除存在重叠的嵌套列表？

我想要编写一段Python代码来移除存在重叠的子列表。这些子列表格式为[lower_bound, upper_bound, data, data]，存储在一个大列表中，目标是遍历大列表并移除所有边界存在重叠的子列表。以下是我当前的实现代码：

def cut_overlapping_ranges(ranges):

  keep_ranges = []
  temp_ranges = ranges

  for range_1 in temp_ranges:
    keep_ranges.append(range_1)
    for range_2 in temp_ranges:
      if range_1 != range_2:
        if ((range_1[0] < range_2[0] < range_1[1]) or (range_1[0] < range_2[1] < range_1[1])):
          temp_ranges.remove(range_2)
  return

当前代码的问题 #

• 遍历中修改列表引发异常：temp_ranges = ranges是对原列表的引用，遍历过程中调用remove会改变列表长度，导致遍历跳过元素或报错
• 重叠判断逻辑不全：仅判断了range_2的边界落在range_1内部的情况，没覆盖range_2完全包含range_1、区间端点重合等场景
• 函数无有效返回：最后return未返回keep_ranges，调用函数无法得到结果
• 逻辑混乱：添加range_1到保留列表后就删除其他重叠项，但未考虑range_1本身可能和已保留的子列表重叠

正确实现方案 #

处理重叠区间的高效方式是先排序，再线性遍历保留不重叠项：

def cut_overlapping_ranges(ranges):
    # 按左边界升序排序，确保处理顺序有序
    sorted_ranges = sorted(ranges, key=lambda x: x[0])
    keep_ranges = []
    
    for current in sorted_ranges:
        # 保留列表为空，或当前区间左边界 >= 最后一个保留区间的右边界，说明无重叠
        if not keep_ranges or current[0] >= keep_ranges[-1][1]:
            keep_ranges.append(current)
    
    return keep_ranges

实现说明 #

• 排序后只需和最后一个保留的区间比较，因为前面的区间左边界更小且不重叠，只要当前区间左边界不小于最后一个的右边界，就不会和任何已保留区间重叠
• 时间复杂度由排序主导，为O(n log n)，比嵌套循环的O(n²)效率更高
• 完整覆盖所有不重叠判断场景，若需要排除端点重合，只需把>=改成>

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