Python中基于跨度长度移除元组列表中的重叠跨度

你的思路方向完全正确——先按跨度长度降序排序，再筛选不与已保留长跨度重叠的项，就能实现需求。我来帮你把这个思路落地，具体步骤和代码如下：

核心逻辑拆解 #

• 排序优先：先把所有跨度按「长度（end - start）」从大到小排序，这样长跨度会被优先处理，后续遇到的短跨度如果和已保留的长跨度重叠，直接丢弃即可。
• 重叠判断：两个跨度 (a, b) 和 (c, d) 重叠的条件是：不是完全不重叠，也就是不满足 b <= c 或 d <= a。换句话说，只要两个区间有交集，就算重叠。
• 筛选保留：维护一个结果列表，遍历排序后的跨度，只有当当前跨度和结果列表里所有已保留的跨度都不重叠时，才把它加入结果列表。最后可以按起始位置重新排序，让结果更规整。

代码实现（Python） #

def keep_longest_non_overlapping(spans):
    # 1. 按跨度长度降序排序，长度相同的话按起始位置升序（可选）
    sorted_spans = sorted(spans, key=lambda x: -(x[1] - x[0]))
    
    result = []
    for current in sorted_spans:
        # 检查当前跨度是否和结果列表中的任何跨度重叠
        overlap = False
        for existing in result:
            # 判断重叠：如果不是完全不重叠，就是重叠
            if not (current[1] <= existing[0] or existing[1] <= current[0]):
                overlap = True
                break
        if not overlap:
            result.append(current)
    
    # 最后按起始位置升序排序，让结果和示例格式一致
    result.sort()
    return result

# 测试示例
original_spans = [(2, 3), (7, 9), (10, 11), (10, 12), (15, 17), (16, 17), (20, 21), (20, 29), (21, 28)]
modified_spans = keep_longest_non_overlapping(original_spans)
print(modified_spans)  # 输出: [(2, 3), (7, 9), (10, 12), (15, 17), (20, 29)]

代码解释 #

1. 排序阶段：用sorted函数，key=lambda x: -(x[1]-x[0])表示按跨度长度的负值排序，也就是降序。如果两个跨度长度相同，默认会按起始位置升序排列，不影响最终结果。
2. 重叠检查：遍历每个已保留的跨度，只要当前跨度和其中任何一个重叠，就标记为overlap=True，跳过该跨度。
3. 结果整理：最后对结果列表按起始位置升序排序，让输出和你给出的示例格式一致。

这个方法逻辑直观，符合你一开始的思路，而且能完美处理示例中的情况，包括多个重叠短跨度对应一个长跨度的场景。

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