如何在Python中清除嵌套线段列表中的子线段

思路说明 #

要删除嵌套子线段，核心是识别出完全被其他线段包含的子线段。我们可以通过以下步骤实现：

• 统一线段格式：将元组或range类型的线段都转换为(start, end)元组，方便后续处理
• 排序线段：按起始点升序排列，若起始点相同则按结束点降序排列，确保包含其他线段的长线段排在前面
• 过滤嵌套线段：遍历排序后的列表，只保留那些结束点大于当前已保留的最后一个线段结束点的线段，自动排除被包含的子线段

实现代码 #

def remove_nested_segments(segments):
    # 统一转换为(start, end)元组
    normalized = []
    for s in segments:
        if isinstance(s, range):
            normalized.append((s.start, s.end))
        else:
            normalized.append((s[0], s[1]))
    
    # 排序：先按起始点升序，起始点相同则按结束点降序
    normalized.sort(key=lambda x: (x[0], -x[1]))
    
    # 过滤嵌套线段
    result = []
    for seg in normalized:
        if not result:
            result.append(seg)
        else:
            last_start, last_end = result[-1]
            # 当前线段的结束点大于最后一个保留线段的结束点，说明不是嵌套
            if seg[1] > last_end:
                result.append(seg)
    
    # 保持原类型返回（如果原列表是range类型，转换回range）
    if segments and isinstance(segments[0], range):
        return [range(s[0], s[1]) for s in result]
    else:
        return result

# 测试元组列表
tuple_segments = [(50, 60), (10, 20), (10, 40), (40, 60), (60, 80), (75, 95), (95, 100)]
print(remove_nested_segments(tuple_segments))
# 输出: [(10, 40), (40, 60), (60, 80), (75, 95), (95, 100)]

# 测试range列表
range_segments = [range(50, 60), range(10, 20), range(10, 40), range(40, 60), range(60, 80), range(75, 95), range(95, 100)]
print(remove_nested_segments(range_segments))
# 输出: [range(10, 40), range(40, 60), range(60, 80), range(75, 95), range(95, 100)]

代码解释 #

• 格式统一：通过判断元素类型，将range转换为元组，确保后续处理逻辑一致
• 排序逻辑：起始点升序保证从左到右处理线段，起始点相同的按结束点降序，让更长的线段先被保留，避免短线段提前加入后遮挡长线段
• 过滤逻辑：只保留结束点更大的线段，排序后前面的线段起始点小于等于当前线段，若当前线段结束点不大于已保留的最后一个线段的结束点，说明它完全被包含在之前的线段中，属于嵌套子线段，直接跳过

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