区间问题：合并、覆盖与调度

区间问题：合并、覆盖与调度

摘要

时间段、会议安排、日志窗口、库存批次和二维坐标范围，都可以抽象为区间问题。区间题看似变化很多，但核心通常是先排序，再维护已经处理部分的边界。本文介绍区间的闭开边界、合并区间、插入新区间、移除重叠区间、最少资源调度和最少射箭数量，并分析排序规则为何会随目标变化。

一、背景与问题

区间常写为 [start, end]，最常见的操作包括：

• 合并所有发生重叠的区间；
• 判断新时间段是否冲突；
• 选择最多互不重叠的活动；
• 计算至少需要多少会议室或服务实例；
• 使用最少点、最少操作覆盖全部区间。

如果逐一比较每一对区间，通常需要 O(n²) 时间。将区间按起点或终点排序后，许多问题可以在线性扫描中完成，整体复杂度降为 O(n log n)。

二、核心概念

1. 闭区间、开区间与相接

区间语义必须先说清楚：

本文合并区间默认使用闭区间，因此 next_start <= current_end 时合并。会议室调度使用半开时间段，结束时刻的会议室可立即给开始时刻的下一场会议使用。

2. 区间题常见排序规则

同样是区间，排序字段不同，原因是优化目标不同。不能把“按起点排序”当作所有区间问题的万能模板。

三、工作原理

1. 合并区间的扫描不变量

按起点排序后，维护一个尚未定稿的当前区间：

下一个区间起点 > 当前右边界 → 当前区间已无法再扩展，写入结果
下一个区间起点 <= 当前右边界 → 两者重叠，扩展当前右边界

由于后续区间起点只会更大，一旦出现间隔，当前区间不可能再与更后面的区间重叠，因此可以安全地写入结果。

2. 调度问题为什么需要堆

合并问题只关心当前合并范围，资源调度则要同时追踪多个仍未结束的区间。最小堆保存所有占用资源的结束时间；堆顶永远是最早释放的资源。

按开始时间处理会议
↓
最早结束时间 <= 当前开始时间？
├─ 是：复用该资源
└─ 否：申请新资源

四、实战示例

1. 合并闭区间

def merge_intervals(intervals):
if any(start > end for start, end in intervals):
raise ValueError("区间起点不能大于终点")
if not intervals:
return []

merged = []
current_start, current_end = sorted(intervals, key=lambda item: item[0])[0]

for start, end in sorted(intervals, key=lambda item: item[0])[1:]:
if start <= current_end:
current_end = max(current_end, end)
else:
merged.append([current_start, current_end])
current_start, current_end = start, end

merged.append([current_start, current_end])
return merged

assert merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]) == [
[1, 6], [8, 10], [15, 18]
]
assert merge_intervals([[1, 4], [4, 5]]) == [[1, 5]]
assert merge_intervals([]) == []

代码先验证输入合法性，再排序并扫描。第二个断言体现了闭区间语义：两个区间端点相接时仍然合并。

2. 插入新区间

已排序且互不重叠的区间列表中插入新区间时，可以将区间分为三段：新区间左侧、与新区间重叠、右侧。

def insert_interval(intervals, new_interval):
start, end = new_interval
if start > end:
raise ValueError("新区间起点不能大于终点")

result = []
index = 0
while index < len(intervals) and intervals[index][1] < start:
result.append(intervals[index])
index += 1

while index < len(intervals) and intervals[index][0] <= end:
start = min(start, intervals[index][0])
end = max(end, intervals[index][1])
index += 1

result.append([start, end])
result.extend(intervals[index:])
return result

assert insert_interval([[1, 3], [6, 9]], [2, 5]) == [[1, 5], [6, 9]]
assert insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) == [
[1, 2], [3, 10], [12, 16]
]

这个实现依赖输入区间已按起点排序且彼此不重叠。如果输入没有保证该前提，应先调用合并逻辑或明确拒绝输入。

3. 移除最少区间使其不重叠

按结束时间升序保留尽可能多的区间，未被保留的数量就是最少移除数。

def erase_overlap_intervals(intervals):
if not intervals:
return 0
if any(start > end for start, end in intervals):
raise ValueError("区间起点不能大于终点")

removed = 0
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda item: item[1]):
if start >= last_end:
last_end = end
else:
removed += 1
return removed

assert erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]) == 1
assert erase_overlap_intervals([[1, 2], [1, 2], [1, 2]]) == 2
assert erase_overlap_intervals([]) == 0

保留结束最早的区间，能给后续区间留下最大的可用空间。这与上一节的活动选择问题是同一类贪心思想。

4. 最少会议室：使用最小堆复用资源

import heapq

def min_meeting_rooms(meetings):
if any(start > end for start, end in meetings):
raise ValueError("会议开始时间不能晚于结束时间")

active_ends = []
for start, end in sorted(meetings, key=lambda item: item[0]):
if active_ends and active_ends[0] <= start:
heapq.heappop(active_ends)
heapq.heappush(active_ends, end)
return len(active_ends)

assert min_meeting_rooms([[0, 30], [5, 10], [15, 20]]) == 2
assert min_meeting_rooms([[7, 10], [2, 4]]) == 1
assert min_meeting_rooms([[1, 2], [2, 3]]) == 1

在半开区间语义下，[1, 2) 结束时，[2, 3) 可以立即复用同一会议室，因此判断为 active_ends[0] <= start。如果业务定义相接也冲突，应改用严格小于。

5. 最少点覆盖区间：引爆气球问题

每个点可以覆盖所有包含该点的闭区间。按右端点从小到大处理，遇到未被当前点覆盖的区间时，就在该区间右端点放一个新点。

def min_cover_points(intervals):
if any(start > end for start, end in intervals):
raise ValueError("区间起点不能大于终点")
if not intervals:
return 0

points = 0
last_point = float("-inf")
for start, end in sorted(intervals, key=lambda item: item[1]):
if start > last_point:
points += 1
last_point = end
return points

assert min_cover_points([[10, 16], [2, 8], [1, 6], [7, 12]]) == 2
assert min_cover_points([[1, 2], [2, 3], [3, 4]]) == 2

在当前区间最右端放点，既覆盖当前区间，又尽量有机会覆盖后续起点更靠右的区间。这是“按结束时间贪心”的另一种形式。

6. 用小规模暴力解验证合并结果

def has_overlap(intervals):
ordered = sorted(intervals)
return any(
ordered[index + 1][0] <= ordered[index][1]
for index in range(len(ordered) – 1)
)

merged = merge_intervals([[5, 7], [1, 2], [2, 4], [8, 8]])
assert merged == [[1, 4], [5, 7], [8, 8]]
assert has_overlap(merged) is False

测试应覆盖空输入、完全包含、端点相接、负数端点、重复区间和已经有序的输入。区间题最常见的错误不是排序本身，而是边界是否应该合并。

五、常见问题与实践建议

1. 没有定义端点语义

start <= current_end 和 start < current_end 的差异会直接改变结果。预约、日志、时间戳和坐标范围可能采用不同规则，函数注释和测试用例必须写明。

2. 一边排序一边修改原始输入

若调用方还需要保留原始区间顺序，使用 sorted() 创建新列表，而不是原地 sort()。同时，返回结果中的区间最好创建新列表，避免无意共享可变对象。

3. 会议室算法只弹出一个已结束会议

本例的目标是最终需要的房间数，单次弹出足够维持堆大小上界；若还要统计当前时刻所有可复用资源或分配具体房间编号，则应在新会议开始前循环弹出所有结束时间不晚于当前开始时间的房间。

4. 错把区间权重忽略掉

如果会议或任务有不同收益，选择最多区间不等于收益最大。带权区间调度需要考虑收益状态，通常使用动态规划加二分查找前驱区间。

六、进阶思考

1. 事件扫描线

当需要知道每个时刻的并发数、最大重叠数或持续时间时，可以把每个区间拆成“开始事件”和“结束事件”，按时间排序后扫描。端点相同的事件谁先处理，仍然取决于闭开区间语义。

2. 区间树与动态更新

本文算法适合离线批量处理。若系统需要频繁插入、删除和查询重叠区间，可以考虑平衡树、区间树、线段树或数据库的范围索引。数据结构的选择取决于更新频率、查询类型和数据规模。

3. 将时间统一为可比较的单位

业务时间应先处理时区、夏令时、精度和结束时间是否包含等规则，再转成统一时间戳参与算法。不要直接比较格式不一致的字符串时间。

结论

区间问题的核心是明确边界语义，再根据优化目标选择排序规则和扫描状态。合并与插入通常按起点排序，选择与覆盖通常按终点排序，资源调度则需要最小堆管理多个活动区间。

写区间算法时，应将“端点相接是否冲突”作为第一条业务规则，并用针对性的边界测试固定下来。下一步可以学习字符串算法，理解匹配、计数和前缀结构如何利用序列中的重复信息。

参考资料

• Python heapq 官方文档
• CP-Algorithms：Scheduling
• CLRS：Greedy Algorithms