如何在Python中合并字典内的重叠范围区间？

问题描述 #

给定以下Python字典，每个键对应一个数值区间（格式为[最小值, 最大值]）：

segments = {
    "seg1": [832, 1283],
    "seg2": [4219, 4670],
    "seg3": [759, 1210],
    "seg4": [3540, 4582],
    "seg5": [599, 1164],
    "seg6": [3843, 4582],
}

需要将字典中存在重叠的区间合并，最终得到代表总范围的单个键值对。示例结果如下：

segments = {
    "seg1": [599, 1283], 
    "seg2": [3540, 4670]
}

实现方案 #

核心思路 #

1. 提取字典中的键值对，按区间的最小值排序，确保按从小到大的顺序处理区间，避免遗漏重叠情况。
2. 遍历排序后的区间，逐个检查是否与已合并的最后一个区间重叠：
   • 若重叠，则更新已合并区间的最大值为两者的较大值；
   • 若不重叠，则将当前区间加入合并列表。
3. 将合并后的列表转换回字典格式，保留每组的第一个键作为新字典的键。

代码实现 #

def merge_overlapping_segments(seg_dict):
    # 将字典键值对转为列表，方便排序
    seg_items = list(seg_dict.items())
    # 按区间的起始值从小到大排序
    seg_items.sort(key=lambda x: x[1][0])
    
    merged_groups = []
    for key, (start, end) in seg_items:
        if not merged_groups:
            # 合并列表为空，直接加入第一个区间
            merged_groups.append([key, start, end])
        else:
            # 获取最后一个已合并的区间信息
            last_key, last_start, last_end = merged_groups[-1]
            # 判断当前区间是否与最后一个合并区间重叠
            if start <= last_end:
                # 重叠则更新区间的最大值
                new_end = max(last_end, end)
                merged_groups[-1] = [last_key, last_start, new_end]
            else:
                # 不重叠则新增一组
                merged_groups.append([key, start, end])
    
    # 转换为目标字典格式
    return {group[0]: [group[1], group[2]] for group in merged_groups}

# 测试示例
original_segments = {
    "seg1": [832, 1283],
    "seg2": [4219, 4670],
    "seg3": [759, 1210],
    "seg4": [3540, 4582],
    "seg5": [599, 1164],
    "seg6": [3843, 4582],
}

merged_result = merge_overlapping_segments(original_segments)
print(merged_result)

代码说明 #

• 排序步骤是关键：只有按区间起始值排序后，才能保证我们可以通过比较当前区间的起始值和上一个合并区间的结束值，来判断是否重叠。
• 合并逻辑：只要当前区间的起始值小于等于上一个合并区间的结束值，就说明两个区间有重叠（或相邻），此时需要将两个区间合并为一个，取最大的结束值作为新的区间终点。
• 最终字典的键：默认使用每组第一个出现的键，如果你想自定义键名（比如用"merged_group_1"这类命名），可以修改最后转换字典的代码逻辑。

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