牛客Top200---合并区间 (Java实战：从图解到代码的完整通关)

1. 合并区间问题初探

第一次看到"合并区间"这个题目时，我脑海中浮现的是小时候玩过的拼图游戏。想象每个区间就像一块拼图碎片，我们需要找出哪些碎片可以拼接在一起，最终形成更大的完整图案。这个类比帮助我快速理解了问题的本质。

合并区间问题的核心是处理一组可能重叠的区间，将它们合并成不重叠的区间集合。在实际开发中，这类问题经常出现在日程安排、资源分配等场景。比如会议室预定系统需要合并相邻的时间段，或者处理多个用户的可用时间段重叠情况。

理解这个问题需要掌握三个基本概念：

1. 区间表示：通常用[start, end]表示，start是起始点，end是结束点
2. 区间关系：两个区间可能存在包含、相交或相离三种关系
3. 合并规则：当两个区间重叠或相邻时，可以合并成一个更大的区间

2. 图解合并区间的三种情况

2.1 相交区间的合并

最典型的情况是两个区间部分重叠。比如区间A=[1,3]和区间B=[2,5]，由于B的起点2位于A的范围内(1≤2≤3)，这两个区间可以合并。合并后的新区间取两个区间的最小起点和最大终点，即[1,5]。

我在白板上画图时发现，这类情况的关键判断点是：后一个区间的start是否小于等于前一个区间的end。如果是，就说明存在重叠，需要合并。

2.2 包含关系的处理

另一种常见情况是完全包含。比如区间A=[1,5]和区间B=[2,3]，B完全在A内部。这种情况下合并结果就是外层的区间A。实际编码时，我们不需要特殊处理这种情况，因为取最大end的规则已经涵盖了这种场景。

2.3 相离区间的处理

当两个区间没有任何重叠时，比如[1,2]和[3,4]，它们应该保持原样不被合并。这是边界条件之一，在算法中表现为：当后一个区间的start大于前一个区间的end时，两个区间独立存在。

3. Java实现的关键步骤

3.1 区间排序的重要性

在动手编码前，我犯过一个典型错误：直接处理未排序的区间列表。这会导致遗漏某些合并机会。比如处理[[2,4],[1,3]]时，如果不先排序，就会错过合并机会。

Java中可以使用Collections.sort配合Lambda表达式实现优雅的排序：

Collections.sort(intervals, (a, b) -> a.start - b.start);

这行代码的意思是：按照每个区间的start值进行升序排列。Lambda表达式(a,b)->a.start-b.start实际上定义了一个比较器，当结果为负时表示a应该排在b前面。

3.2 合并算法的核心逻辑

合并过程的核心是一个循环遍历，比较当前区间与前一个合并结果的关系。我的实现方案是：

1. 初始化结果集，先加入第一个区间
2. 从第二个区间开始遍历：
   • 如果当前区间与结果集最后一个区间重叠，则合并它们
   • 否则将当前区间加入结果集
3. 最后返回结果集

这个方案的优势是只需要一次遍历，时间复杂度是O(n)，加上排序的O(nlogn)，整体复杂度保持在O(nlogn)。

4. 完整代码实现与优化

4.1 基础版本实现

基于上述思路，完整的Java实现如下：

public List<Interval> merge(List<Interval> intervals) { if (intervals == null || intervals.size() <= 1) { return intervals; } // 按start升序排序 intervals.sort((a, b) -> a.start - b.start); List<Interval> result = new ArrayList<>(); Interval current = intervals.get(0); result.add(current); for (Interval next : intervals) { if (next.start <= current.end) { // 有重叠 current.end = Math.max(current.end, next.end); } else { // 无重叠 current = next; result.add(current); } } return result; }

4.2 边界情况处理

在实际编码中，我发现几个需要特别注意的边界情况：

1. 空列表输入：直接返回空列表
2. 单个区间：无需合并，直接返回
3. 完全相同的区间：需要去重
4. 大数边界：注意整型溢出问题

4.3 性能优化技巧

经过多次测试，我总结出几个优化点：

1. 使用List的sort方法代替Collections.sort，语法更简洁
2. 避免频繁创建新Interval对象，直接修改end值
3. 对于超大区间集合，可以考虑并行排序

5. 调试与测试实战

5.1 单元测试用例设计

为了验证算法正确性，我设计了以下几组测试用例：

1. 常规情况：[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
2. 完全包含：[[1,4],[2,3]] → [[1,4]]
3. 不相交：[[1,2],[3,4]] → [[1,2],[3,4]]
4. 单个区间：[[1,3]] → [[1,3]]
5. 空输入：[] → []

5.2 常见错误排查

在实现过程中，我遇到过几个典型错误：

1. 忘记处理空列表输入，导致NullPointerException
2. 合并时错误地创建了新Interval对象，造成内存浪费
3. 没有考虑所有区间都合并的情况
4. 排序时使用了错误的比较逻辑

5.3 可视化调试技巧

对于复杂的区间集合，我采用打印中间结果的方式辅助调试：

System.out.println("当前结果：" + result); System.out.println("处理区间：" + next.start + "-" + next.end);

这种方法虽然原始，但对于理解算法执行过程非常有效。

6. 算法复杂度分析

6.1 时间复杂度分解

整个算法的时间消耗主要来自两个部分：

1. 排序操作：使用Java的TimSort算法，时间复杂度为O(nlogn)
2. 线性扫描：单次遍历O(n) 因此总体时间复杂度为O(nlogn)，这在处理大规模数据时表现良好。

6.2 空间复杂度考量

空间复杂度取决于实现方式：

1. 原地修改：O(1)额外空间（但会破坏输入）
2. 创建新列表：O(n)空间 通常选择后者以保持函数的纯净性，即不修改输入参数。

7. 实际应用场景扩展

7.1 会议室安排问题

这是合并区间的经典应用场景。给定一组会议时间区间，计算最少需要多少会议室。解法是先合并所有重叠区间，然后统计剩余区间数量。

7.2 日程合并功能

在日历应用中，合并多个来源的日程安排时，需要合并重叠的时间段以消除重复。这正是合并区间算法的直接应用。

7.3 游戏开发中的碰撞检测

在游戏开发中，物体的有效碰撞区间可以通过合并算法优化，减少不必要的检测计算。