Python基于相邻区间差值条件合并/压缩区间列表的实现问题

示例输入 #

a = [[0, 1], [3, 4], [5, 11], [12, 17], [20, 25], [26, 28]]

期望输出 #

[[0,1], [3,17], [20,28]]

合并规则 #

• 逐对遍历相邻区间，若前一个区间的末尾值与后一个区间的首值的差值小于2，则将两个区间合并
• 合并后新区间的下界为前序区间的下界，上界为后序区间的上界
• 合并操作支持连续执行：示例中[3, 4]、[5, 11]、[12, 17]三个相邻区间连续满足合并条件，最终合并为[3,17]

原有代码问题 #

原有实现存在3个核心逻辑错误：

1. 取值错误：获取后一个区间的首值时，错取成了后一个区间的上界a[i+1][1]，正确取值应为a[i+1][0]
2. 比较基准错误：每次判断合并条件时，应该用当前已经完成合并的区间上界做比较，而不是原数组中未合并的第i个区间的上界，否则无法处理连续合并的场景
3. 边界遗漏：循环结束后没有把最后一段合并完成的区间追加到结果列表中

正确实现代码 #

a = [[0, 1], [3, 4], [5, 11], [12, 17], [20, 25], [26, 28]]
b = []
if a:
    # 初始化当前待合并区间的上下界
    curr_lower, curr_upper = a[0]
    for lower, upper in a[1:]:
        # 满足合并条件：下一个区间首值 和 当前区间上界 的差小于2
        if lower - curr_upper < 2:
            # 更新当前合并区间的上界
            curr_upper = upper
        else:
            # 不满足合并条件，将已合并完成的区间存入结果
            b.append([curr_lower, curr_upper])
            # 重置待合并区间为当前遍历到的新区间
            curr_lower, curr_upper = lower, upper
    # 追加最后一段合并完成的区间
    b.append([curr_lower, curr_upper])

print(b)

运行上述代码可以直接得到期望输出。

逻辑说明 #

• 遍历开始前先取第一个区间作为初始的待合并区间
• 从第二个区间开始逐个遍历，每次判断当前待合并区间是否能和下一个区间合并
• 满足合并条件时只更新待合并区间的上界，继续向后查找可连续合并的区间
• 不满足合并条件时，把已经合并完成的区间存入结果列表，将当前遍历到的区间设为新的待合并区间
• 遍历结束后追加最后一段待合并区间，避免遗漏最后一段结果

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