外观
10 - 区间问题统一解法:会议冲突、合并与并发峰值
前置阅读:08 - 排序算法怎么选。
本文负责区间端点、合并和扫描线模型;“选择最多任务”的证明统一见20 - 贪心算法与正确性证明。
摘要
两场会议首尾相接,是否需要两个房间?多个预约覆盖了哪些连续时间段?一天内最多有多少连接同时在线?这些问题都可以把一次占用表示为一个区间,再按端点顺序处理。
本文先定义区间边界,再解释如何合并覆盖范围、统计最大并发数,以及为什么最大并发数就是所需会议室数量。IP 段合并也涉及区间覆盖,但 IP 地址是离散值,不能直接照搬时间区间的端点规则。
1. 先定义端点语义
本文默认半开区间 [start, end):开始时刻包含,结束时刻不包含。因此 [10, 11) 与 [11, 12) 不冲突。
“半开”指只包含一端;闭区间 [start, end] 则包含两端。对两个非空半开区间 [a,b) 和 [c,d),只有 a < d 且 c < b 时才重叠,也就是存在共同占用的时刻。如果业务使用闭区间,边界判断和同时间事件排序必须相应修改。
本文代码的正常输入前提是数组和元素均非 null,每个区间满足 start < end,所有端点使用同一时间单位和时间基准。start == end 的半开区间为空,start > end 则是反向区间;现有代码没有校验或过滤它们,第 6 节说明这些输入的处理边界。
2. 合并区间
合并要得到所有区间覆盖的范围,而不是统计有多少任务。先按起点从小到大排序,再维护已经合并的结果:
- 结果为空,或最后一段的终点小于新区间起点:中间有空隙,另开一段。
- 否则两段重叠或首尾相接:保留原起点,把终点更新为两者终点的最大值。
为什么只看最后一段?排序后,新区间的起点不会早于已处理区间的起点;结果中更早的段已经与最后一段分离,因此也不可能与新区间相连。合并时必须比较当前合并结果的终点:例如 [1,10)、[2,3)、[4,5) 中,第三段虽然不与第二个原区间重叠,却仍被第一段覆盖。
下面是局部代码,方法需放入 Java 类中,record 用于表示带有起点和终点的记录;第 5 节提供包含入口的完整类。这里的 merge 会直接排序传入数组,改变元素顺序。
java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
record Interval(int start, int end) {}
static List<Interval> merge(Interval[] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(Interval::start));
List<Interval> result = new ArrayList<>();
for (Interval current : intervals) {
if (
result.isEmpty() || result.get(result.size() - 1).end() < current.start()
) {
result.add(current);
} else {
Interval last = result.remove(result.size() - 1);
result.add(
new Interval(last.start(), Math.max(last.end(), current.end()))
);
}
}
return result;
}对于半开区间,是否把端点相接视为可合并要由业务决定。上例使用 <,因此 [1,2) 与 [2,3) 会合并为 [1,3);若业务只合并真正重叠区间,应改为 <=,让二者保持分离。
所以,“是否同时占用资源”与“是否压缩成一段连续覆盖范围”要分别定义。上例选择合并首尾相接的区间,但不把它们算作冲突。
3. 扫描线统计并发峰值
扫描线是沿时间轴按顺序处理事件的方法。并发数只会在区间开始或结束时变化,所以不必逐个时刻统计:把每个区间拆成开始 +1、结束 -1 两个事件,再按时间排序。
current 保存已处理事件的变化量之和,这叫前缀累加;同一时刻的事件全部处理完后,它就是该时刻仍在占用资源的区间数。best 保存扫描过程中达到的最大值。下面的局部代码复用上一节的 Interval 和导入。
java
record Event(int time, int delta) {}
static int maxConcurrent(Interval[] intervals) {
List<Event> events = new ArrayList<>();
for (Interval interval : intervals) {
events.add(new Event(interval.start(), 1));
events.add(new Event(interval.end(), -1));
}
events.sort(
Comparator.comparingInt(Event::time).thenComparingInt(Event::delta)
); // 同时刻先处理 -1
int current = 0;
int best = 0;
for (Event event : events) {
current += event.delta();
best = Math.max(best, current);
}
return best;
}半开区间下,同一时刻要先处理结束事件,避免把首尾相接算作并发。例如 [10,11) 与 [11,12):到 11 时先减到 0,再加到 1,峰值仍为 1;若先加再减,就会产生不存在的峰值 2。代码先比较 time,相等时再比较 delta,因此 -1 排在 +1 前面。
若改成闭区间,两段在 11 时都占用资源,就应先处理开始事件。事件顺序来自端点是否被包含,而不是任意的排序习惯。
4. 会议室数量
假设每场会议占用一个房间,房间之间可互换,且会议结束后可以立即复用。那么同时进行的会议有多少场,就至少需要多少个房间;按开始时间安排时,复用已释放的房间,只在没有空房时增加房间,因此最少房间数等于最大并发数。
除了扫描线,也可以按开始时间排序,用小顶堆维护正在进行会议的结束时间。小顶堆能直接查看当前最小值,这里就是最早结束的会议。新会议开始前,反复弹出结束时间 <= 当前起点的会议,再加入新会议的终点,堆大小就是此时占用的房间数。只要堆顶尚未结束,其余会议也都没有结束,因此不用逐个检查。
若只需要最大并发数,事件排序直接表达了计数过程;若还需要知道每个会议复用了哪个具体房间,则要在堆中保存房间标识和结束时间,并维护可复用房间。下面的示例只计算数量,不输出分配方案。
5. 完整可运行示例:合并与会议室
下面的类对应文件名 IntervalDemo.java,包含 main 入口;输入前提与第 1 节相同。与第 2 节的局部方法不同,这里的两个方法都先复制数组,不改变调用方的元素顺序。代码使用 record,需要支持该语法的 JDK。
java
import java.util.*;
/**
* 可运行示例:区间问题统一解法:会议冲突、合并与并发峰值。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class IntervalDemo {
record I(int start, int end) {}
static List<I> merge(I[] input) {
I[] a = Arrays.copyOf(input, input.length);
// 起点有序后,新区间只可能与当前结果的最后一个区间重叠。
Arrays.sort(a, Comparator.comparingInt(I::start));
List<I> out = new ArrayList<>();
for (I x : a) {
if (out.isEmpty() || out.get(out.size() - 1).end() < x.start()) out.add(
x
);
else {
// 重叠时保留较早起点,并把右边界扩展到两者最大值。
I last = out.remove(out.size() - 1);
out.add(new I(last.start(), Math.max(last.end(), x.end())));
}
}
return out;
}
static int rooms(I[] input) {
I[] a = Arrays.copyOf(input, input.length);
Arrays.sort(a, Comparator.comparingInt(I::start));
// 小顶堆保存所有仍在进行中的会议结束时刻。
PriorityQueue<Integer> ends = new PriorityQueue<>();
int best = 0;
for (I x : a) {
// 半开区间下,结束时间 <= 当前开始时间的会议已释放房间。
while (!ends.isEmpty() && ends.peek() <= x.start()) ends.poll();
ends.offer(x.end());
// 堆大小就是此刻同时占用的房间数。
best = Math.max(best, ends.size());
}
return best;
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
I[] a = { new I(0, 30), new I(5, 10), new I(15, 20) };
System.out.println(merge(a));
System.out.println(rooms(a));
}
}手工推演会议室数量
对 [0,30)、[5,10)、[15,20),按开始时间处理:
| 当前会议 | 加入前释放的结束时间 | 加入后仍活跃的结束时间 | 当前数量 | 历史峰值 |
|---|---|---|---|---|
[0,30) | 无 | {30} | 1 | 1 |
[5,10) | 无 | {10,30} | 2 | 2 |
[15,20) | 10 | {20,30} | 2 | 2 |
表中用集合形式列出结束时间,不表示堆的内部排列。手工推导可得:merge(a) 覆盖范围为 [0,30),rooms(a) 返回 2;这些是预期结果,不是实际运行记录。
不变量是每轮处理后都成立的约束。合并算法的结果始终按起点有序,覆盖所有已处理区间,且相邻结果之间有空隙;会议室算法在加入当前会议后,堆中只保留当前仍活跃会议的结束时间。这些约束解释了为什么只比较最后一段或堆顶就够了。
令 n 为区间数,按一次整数比较为常数成本分析:合并在排序后只扫描一次;扫描线排序 2n 个事件后逐个累加;会议室算法中每个结束时间至多入堆、出堆各一次。三者总体时间均为 O(n log n)。结果列表、事件列表,以及完整示例中的数组副本和堆,额外空间均为 O(n) 量级;这里不据此比较实际耗时。
6. 验证与排障
以下是测试与排障建议:
对端点为小整数的半开区间,可把 [t,t+1) 作为一个时间片,逐片统计满足 start <= t < end 的区间数,取最大值作为暴力基线,也就是直接枚举得到的对照答案。再与扫描线和会议室算法比较。合并结果则应检查覆盖范围是否与输入一致、是否有序,以及相接区间是否按业务规则合并。
测试应覆盖空输入、单区间、完全包含、首尾相接、相同起点、同一时刻大量开始和结束,以及接近整数上下界的端点。另需单独检查零长度和非法反向区间:现有代码不会拒绝它们。静态推演单个 [1,1) 时,rooms 仍会返回 1,而半开空区间并不占用房间;扫描线会先处理结束事件,使中间计数短暂变成负数。因此,业务若允许空区间,应在进入计数算法前明确过滤策略;反向区间也应先校验,不能把现有返回值当作有效答案。本文保留原代码行为。
线上并发峰值异常时,先核对时间单位、时区、事件排序和区间结束是否真实上报,再检查算法。若从真实事件流累加计数,缺失某个结束事件会让对应的占用一直不被扣除;长期累积可能表现为“并发永不下降”。这属于数据协议问题。本文函数接收完整区间,默认每条记录都已具备两个端点,并未实现事件采集。
7. 容易踩的坑
- 没有明确
[start,end)还是[start,end]。 - 同时间开始与结束事件排序错误。
- 合并时只比较相邻原区间,而没有与当前合并结果比较。
- 在比较器(
Comparator)中用时间戳相减判断大小,差值可能溢出;示例使用comparingInt比较端点。 - 未先处理时区和夏令时,就把本地时间直接当作同一时间轴上的整数。应先得到含义一致的端点,再进行排序。
- 把“不冲突”与“合并后是否连续”当成同一条业务规则。
8. 总结
区间算法的核心是先统一端点语义,再通过排序让局部比较足以决定全局关系。
- 开闭区间决定重叠与同时间事件顺序;相接区间是否合并还需业务约定。
- 合并区间只需维护当前最右边界。
- 扫描线把区间问题转换为有序事件上的前缀累加。
需要从区间中选择最多任务时,继续阅读贪心算法与正确性证明。进入递归主线可阅读递归、调用栈与问题缩减。