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

1. 合并区间问题初探第一次看到合并区间这个题目时我脑海中浮现的是小时候玩过的拼图游戏。想象每个区间就像一块拼图碎片我们需要找出哪些碎片可以拼接在一起最终形成更大的完整图案。这个类比帮助我快速理解了问题的本质。合并区间问题的核心是处理一组可能重叠的区间将它们合并成不重叠的区间集合。在实际开发中这类问题经常出现在日程安排、资源分配等场景。比如会议室预定系统需要合并相邻的时间段或者处理多个用户的可用时间段重叠情况。理解这个问题需要掌握三个基本概念区间表示通常用[start, end]表示start是起始点end是结束点区间关系两个区间可能存在包含、相交或相离三种关系合并规则当两个区间重叠或相邻时可以合并成一个更大的区间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 合并算法的核心逻辑合并过程的核心是一个循环遍历比较当前区间与前一个合并结果的关系。我的实现方案是初始化结果集先加入第一个区间从第二个区间开始遍历如果当前区间与结果集最后一个区间重叠则合并它们否则将当前区间加入结果集最后返回结果集这个方案的优势是只需要一次遍历时间复杂度是O(n)加上排序的O(nlogn)整体复杂度保持在O(nlogn)。4. 完整代码实现与优化4.1 基础版本实现基于上述思路完整的Java实现如下public ListInterval merge(ListInterval intervals) { if (intervals null || intervals.size() 1) { return intervals; } // 按start升序排序 intervals.sort((a, b) - a.start - b.start); ListInterval 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 边界情况处理在实际编码中我发现几个需要特别注意的边界情况空列表输入直接返回空列表单个区间无需合并直接返回完全相同的区间需要去重大数边界注意整型溢出问题4.3 性能优化技巧经过多次测试我总结出几个优化点使用List的sort方法代替Collections.sort语法更简洁避免频繁创建新Interval对象直接修改end值对于超大区间集合可以考虑并行排序5. 调试与测试实战5.1 单元测试用例设计为了验证算法正确性我设计了以下几组测试用例常规情况[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]完全包含[[1,4],[2,3]] → [[1,4]]不相交[[1,2],[3,4]] → [[1,2],[3,4]]单个区间[[1,3]] → [[1,3]]空输入[] → []5.2 常见错误排查在实现过程中我遇到过几个典型错误忘记处理空列表输入导致NullPointerException合并时错误地创建了新Interval对象造成内存浪费没有考虑所有区间都合并的情况排序时使用了错误的比较逻辑5.3 可视化调试技巧对于复杂的区间集合我采用打印中间结果的方式辅助调试System.out.println(当前结果 result); System.out.println(处理区间 next.start - next.end);这种方法虽然原始但对于理解算法执行过程非常有效。6. 算法复杂度分析6.1 时间复杂度分解整个算法的时间消耗主要来自两个部分排序操作使用Java的TimSort算法时间复杂度为O(nlogn)线性扫描单次遍历O(n) 因此总体时间复杂度为O(nlogn)这在处理大规模数据时表现良好。6.2 空间复杂度考量空间复杂度取决于实现方式原地修改O(1)额外空间但会破坏输入创建新列表O(n)空间 通常选择后者以保持函数的纯净性即不修改输入参数。7. 实际应用场景扩展7.1 会议室安排问题这是合并区间的经典应用场景。给定一组会议时间区间计算最少需要多少会议室。解法是先合并所有重叠区间然后统计剩余区间数量。7.2 日程合并功能在日历应用中合并多个来源的日程安排时需要合并重叠的时间段以消除重复。这正是合并区间算法的直接应用。7.3 游戏开发中的碰撞检测在游戏开发中物体的有效碰撞区间可以通过合并算法优化减少不必要的检测计算。