如何从元组范围列表中移除重叠项并保留最长范围？

给定一组范围元组列表，需实现以下处理规则：

• 移除重叠的范围元组；
• 重叠项中保留最长的范围；
• 若重叠项长度相同，则全部保留。

示例 #

输入：

input = [ [(1, 7), (2, 3),  (7, 8), (9, 20)], [(4, 7), (2, 3),  (7, 10)], [(1, 7), (2, 3),  (7, 8)]]

预期输出：

expected_output = [ [(1,7), (9,20)], [(4,7), (2, 3), (7,10)], [(1,7)] ]

现有代码无法满足需求，需进行修改：

def overlap(x:tuple, y:tuple) -> bool:
    return  bool(len( range(max(x[0],y[0]), min(x[1], y[1])+1  ) ))

def drop_overlaps(tuples: list):

    def other_tuples(elems: list, t: tuple)-> list:
        return [e for e in elems if e != t]
        
    return [ t for t in tuples if not any( overlap(t, other_tuple) 
                                            for other_tuple in other_tuples(tuples, t))  ]

修改后的代码 #

def overlap(x: tuple, y: tuple) -> bool:
    # 判断两个范围是否重叠（包含端点接触的情况，比如(1,7)和(7,8)算重叠）
    return max(x[0], y[0]) <= min(x[1], y[1])

def range_length(t: tuple) -> int:
    # 计算范围的长度
    return t[1] - t[0]

def drop_overlaps(tuples: list) -> list:
    # 复制原列表，避免修改原始数据
    remaining = tuples.copy()
    
    i = 0
    while i < len(remaining):
        current = remaining[i]
        current_len = range_length(current)
        # 收集所有与当前元组重叠的其他项
        overlapped = [t for t in remaining if t != current and overlap(current, t)]
        
        if overlapped:
            # 找出重叠组中的最大长度
            max_len = max(range_length(t) for t in overlapped + [current])
            # 如果当前元组长度小于最大值，直接移除
            if current_len < max_len:
                remaining.pop(i)
                continue
            # 若当前元组是最长项，移除所有比它短的重叠项
            else:
                to_remove = [t for t in overlapped if range_length(t) < max_len]
                for t in to_remove:
                    remaining.remove(t)
        # 继续处理下一个元素
        i += 1
    
    return remaining

# 测试示例
input_list = [ [(1, 7), (2, 3),  (7, 8), (9, 20)], [(4, 7), (2, 3),  (7, 10)], [(1, 7), (2, 3),  (7, 8)]]
expected_output = [ [(1,7), (9,20)], [(4,7), (2, 3), (7,10)], [(1,7)] ]

# 对每个子列表分别处理
output = [drop_overlaps(sublist) for sublist in input_list]
print(output == expected_output)  # 输出True

逻辑说明 #

1. 重叠判断优化：替换原range计算长度的方式，直接通过端点比较判断重叠，效率更高且逻辑一致。
2. 新增长度计算函数：封装range_length统一计算范围长度，简化后续比较逻辑。
3. 遍历筛选逻辑：
   • 遍历每个元组，找出所有重叠的其他项；
   • 计算重叠组的最大长度，若当前元组长度小于最大值则移除；
   • 若当前元组是最长项（或长度相同），则移除所有更短的重叠项；
   • 长度相同的重叠项会被保留。
4. 嵌套列表处理：原输入为嵌套列表，需对每个子列表单独调用drop_overlaps函数。

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