1. 概述
在实际开发中，我们经常会遇到一个经典问题：如何检测多个区间之间是否存在重叠。这类问题在日程安排、资源分配、时间轴展示等场景中非常常见。
本文将从定义开始，逐步讲解如何识别重叠区间，并提供两种常见解法：暴力法和扫描线法（Sweep Line），帮助你在面对此类问题时能快速找到最优解。
2. 基本概念
2.1 什么是重叠区间
我们假设有一条从 1 到 ∞ 的直线，上面覆盖了多个区间。如果两个区间 至少有一个点是重合的，那么我们认为它们是重叠的（Overlapping）。
数学定义如下：
给定两个区间 [L₁, R₁] 和 [L₂, R₂]：
✅ 重叠条件：max(L₁, L₂) ≤ min(R₁, R₂)
❌ 不重叠条件：max(L₁, L₂) > min(R₁, R₂)
举个例子：
这两个区间 [1, 4] 和 [2, 5] 是重叠的，因为 max(1, 2) = 2 ≤ min(4, 5) = 4。
反之，如果两个区间没有任何交集，如下图所示：
它们就是非重叠区间（Non-overlapping）。
2.2 问题描述
我们有 n 个区间 [Li, Ri]，需要：
- 找出所有与至少一个其他区间存在重叠的区间
- 返回这些区间的集合
例如，给定以下区间：
输出应为：{1, 2, 3, 5, 6}，因为这些区间至少与另一个区间有交集。
3. 暴力解法（Naive Approach）
✅ 思路
对每个区间，遍历所有其他区间，检查是否重叠。一旦发现重叠，就将当前区间加入结果集。
⚠️ 注意
- 一旦发现当前区间与其他区间重叠，就可以立即加入结果集并 break
- 不需要重复添加同一个区间
Java 示例代码
List<Interval> findOverlappingIntervals(List<Interval> intervals) {
List<Interval> result = new ArrayList<>();
for (int i = 0; i < intervals.size(); i++) {
Interval a = intervals.get(i);
for (int j = 0; j < intervals.size(); j++) {
if (i == j) continue;
Interval b = intervals.get(j);
if (Math.max(a.start, b.start) <= Math.min(a.end, b.end)) {
result.add(a);
break;
}
}
}
return result;
}
时间复杂度
- **O(n²)**，其中 n 是区间数量
踩坑提醒
- 当 n 较大时（如 10⁴ 以上），性能急剧下降，容易超时
- 不适合大规模数据集
4. 扫描线法（Sweep Line Approach）
4.1 核心思想
将每个区间的起始点和结束点视为事件，按顺序扫描这些事件，并维护一个当前“打开”的区间（即当前正在处理的区间）。
事件类型：
start：区间开始end：区间结束
扫描过程中：
- 遇到
start：- 如果当前没有打开的区间，将其设为当前打开区间
- 否则说明当前区间与之前打开的区间重叠，将两者加入结果集
- 遇到
end：- 如果是当前打开的区间，则关闭它
4.2 实现步骤
- 构造事件列表：每个区间有两个事件（start 和 end）
- 按照位置排序事件列表，若位置相同，start 事件优先
- 遍历事件，维护当前打开区间，并判断是否重叠
Java 示例代码
class Event {
int position;
char type; // 'S' for start, 'E' for end
int index;
public Event(int position, char type, int index) {
this.position = position;
this.type = type;
this.index = index;
}
}
List<Interval> sweepLine(List<Interval> intervals) {
List<Event> events = new ArrayList<>();
for (int i = 0; i < intervals.size(); i++) {
Interval interval = intervals.get(i);
events.add(new Event(interval.start, 'S', i));
events.add(new Event(interval.end, 'E', i));
}
// 排序：先按位置，再按类型（start 在 end 前）
events.sort((a, b) -> {
if (a.position != b.position) return Integer.compare(a.position, b.position);
return a.type == 'S' ? -1 : 1;
});
Set<Integer> result = new HashSet<>();
int currentOpen = -1;
for (Event e : events) {
if (e.type == 'S') {
if (currentOpen != -1) {
result.add(e.index);
result.add(currentOpen);
} else {
currentOpen = e.index;
}
} else {
if (e.index == currentOpen) {
currentOpen = -1;
}
}
}
return result.stream().map(intervals::get).collect(Collectors.toList());
}
时间复杂度
- **O(n log n)**，主要来自排序操作
踩坑提醒
- 排序逻辑必须正确处理相同位置的 start 和 end 事件顺序
- 需要避免重复添加同一个区间（使用 Set）
4.3 示例执行过程
以如下区间为例：
事件列表如下（按排序后）：
| position | type | index |
|---|---|---|
| 1 | S | 0 |
| 2 | S | 2 |
| 3 | E | 0 |
| 4 | S | 1 |
| 5 | E | 2 |
| 6 | E | 1 |
| 7 | S | 3 |
| 8 | E | 3 |
| 9 | S | 4 |
| 10 | S | 5 |
| 11 | E | 4 |
| 12 | E | 5 |
执行过程中，重叠区间会被逐步识别出来，最终结果为 {0, 1, 2, 4, 5}，对应原图中的 {1, 2, 3, 5, 6}。
5. 总结
| 方法 | 时间复杂度 | 是否推荐 | 适用场景 |
|---|---|---|---|
| 暴力解法 | O(n²) | ❌ | 小数据量，n < 1000 |
| 扫描线法 | O(n log n) | ✅ | 大数据量，通用场景 |
✅ 最佳实践建议
- 尽量避免暴力解法，尤其是在数据量较大的场景
- 扫描线法是处理区间重叠问题的通用解法，建议熟练掌握
- 注意事件排序的细节处理，避免逻辑错误
如果你在实际项目中遇到类似问题，不妨尝试扫描线法，它不仅能解决重叠检测，还能扩展用于统计重叠次数、找出最多重叠区域等问题。