← 中文资源

简体中文版本

合并重叠区间

规范化半开区间,合并重叠或相邻范围,并用清晰的校验错误拒绝非法边界。

阅读英文原文

功能说明

merge_intervals 接收一组半开区间 [start, end),先按起点排序,再线性扫描合并重叠部分。默认情况下,前一个区间的结束等于后一个区间的开始也会被合并,因为两者在时间轴上连续;传入 adjacent=False 可以只合并真正重叠的区间。它适合预约时间段、日志时间窗、IP 范围和资源占用统计。

Interval 是不可变数据类,构造时校验边界为整数且起点严格小于终点,避免产生空区间或反向区间。合并结果仍使用新的 Interval 对象,不会修改输入。空输入返回空列表,输入可以混用 Interval 实例和二元组。

关键代码

排序后只需比较当前区间与结果列表最后一个区间:

previous = merged[-1]
touches = (
    interval.start <= previous.end
    if adjacent
    else interval.start < previous.end
)
if touches:
    merged[-1] = Interval(
        previous.start,
        max(previous.end, interval.end),
    )
else:
    merged.append(interval)

保留较大的结束位置,可以正确处理一个区间完全包含另一个区间的情况。

使用注意

区间语义是左闭右开,因此 [1,3) 与 [3,5) 在 adjacent=True 时合并为 [1,5),在 False 时保持两段。若业务使用闭区间,需要先转换,否则相邻判断会差一位。起点和终点必须是整数,布尔值会被明确拒绝;浮点数也不在支持范围内,需要更高精度时应使用 Decimal 或刻度化整数。

排序依赖数据类的 order=True,先按起点再按终点;相同起点的区间会先处理较短的一个,但合并结果仍然正确。输入可以是生成器,函数会一次性消费。非法区间会在构造时抛 ValueError,类型错误抛 TypeError,调用方应分别处理。该函数不计算总覆盖长度或间隙,需要时可在结果上再遍历。

验证方式

示例输入 [(1,3),(2,6),(8,10),(10,12),(20,21)],默认输出 [1,6)、[8,12)、[20,21);关闭相邻合并后 [8,10) 与 [10,12) 保持分离。空输入返回空列表。传入 (5,5) 应输出 invalid interval [5, 5),混入字符串边界应输出 interval bounds must be integers。