如何从区间列表中筛选出最长的非重叠区间？

需求 #

从一个列表中选取多个不同的非重叠区间，仅保留最长的那些。

原始数据 #

data = [
    "5628-6203",
    "4753-5325",
    "4690-5322",
    "4684-4923",
    "5652-6191",
    "5628-6203",
    "5628-6203", 
    "5628-6203",
    "17333-17563",
    "17333-17569",
    "17333-17557"
]

实现代码 #

# 解析并排序数据
ranges = [tuple(map(int, item.split('-'))) for item in data]
ranges.sort(key=lambda x: x[0])

# 寻找最长非重叠区间
non_overlapping_ranges = []
current_range = ranges[0]

for r in ranges[1:]:
    # 检查是否重叠
    if r[0] <= current_range[1]:
        # 合并重叠区间
        current_range = (current_range[0], max(current_range[1], r[1]))
    else:
        # 将前一个区间加入结果
        non_overlapping_ranges.append(current_range)
        # 切换到下一个区间
        current_range = r

# 添加最后一个区间
non_overlapping_ranges.append(current_range)

# 按区间长度排序，获取最长区间
longest_ranges = sorted(non_overlapping_ranges, key=lambda x: x[1] - x[0], reverse=True)

print(longest_ranges)

预期输出（适配大规模数据） #

[(4690, 5322), (5628, 6203), (17333,17569)]

内容的提问来源于stack exchange，提问作者Marcin Tomasz Gradowski