Python检测嵌套列表数值区间重叠并保留非重叠项方法

核心处理规则：仅剔除被其他子列表区间完全包含的项，部分重叠但互不包含的项全部保留，每组存在包含关系的项仅保留覆盖范围最大的那个。

实现逻辑 #

• 先对所有子列表排序：按区间起始值升序排列，如果起始值相同，按区间结束值降序排列。同起点的长区间会排在前面，为后续单次遍历过滤做准备。
• 遍历排序后的列表，维护一个遍历过程中遇到的最大区间结束值标记：
  • 如果当前子列表的区间结束值大于历史最大结束值，说明这个区间没有被任何之前的区间包含，后续区间的起始值都大于等于当前区间起始值，也不可能反过来包含它，直接保留，同时更新最大结束值标记。
  • 如果当前子列表的区间结束值小于等于历史最大结束值，说明一定存在一个之前的区间，起始值小于等于当前区间、结束值大于等于当前区间，即当前区间被完全包含，直接剔除。

代码实现 #

注意不要用list作为变量名，会覆盖Python内置列表类型：

# 原始输入数据集
feature_list = [
    [7, 11, 'Feature01'],
    [2, 6, 'Feature02'],
    [31, 59, 'Feature03'],
    [31, 41, 'Feature04'],
    [20, 40, 'Feature05'],
    [25, 30, 'Feature06']
]

# 按规则排序：起点升序，同起点则终点降序
sorted_features = sorted(feature_list, key=lambda x: (x[0], -x[1]))

filtered_result = []
max_end = float('-inf')
for item in sorted_features:
    current_start, current_end, feature_name = item
    if current_end > max_end:
        filtered_result.append(item)
        max_end = current_end

print(filtered_result)

运行结果 #

[[2, 6, 'Feature02'], [7, 11, 'Feature01'], [20, 40, 'Feature05'], [31, 59, 'Feature03']]

结果符合预期：被完全包含的Feature04、Feature06被剔除，其余互不包含的项全部保留。这个方案时间复杂度为O(n log n)，比两两对比检查的O(n²)方案效率高很多，适合数据量较大的场景。

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