【忍者算法】从日程安排到区间合并：探索合并区间问题｜LeetCode 56 合并区间

从日程安排到区间合并：探索合并区间问题

生活中的算法

想象你是一位活动策划师，桌上摆着许多便利贴，每张写着不同的活动时间段：9:00-11:00的晨会、10:30-12:00的培训、14:00-16:00的项目汇报、15:00-17:00的团队建设...有些活动时间明显重叠了，为了让日程更清晰，你需要将这些重叠的时间段合并起来。比如晨会和培训重叠了，就可以合并为9:00-12:00的一个大时间段。
这种情况在生活中随处可见。比如医院的预约时段合并、健身房的预定时间优化、公司会议室的档期管理，甚至是地铁维修时段的规划等。
问题描述

LeetCode第56题"合并区间"是这样描述的：给出一个区间的集合，请合并所有重叠的区间。
例如：

1. 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
2. 输出：[[1,6],[8,10],[15,18]]
3. 解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]

复制代码

最直观的解法：暴力合并

就像你整理日程表一样，最直观的方法是：拿起每张便利贴，和其他所有便利贴比较，看看能否合并。
让我们用一个简单的例子来理解：

1. 时间段：[[1,4], [2,3], [3,6]]
2. 1. 比较[1,4]和[2,3]：
3.    2在1-4之间，合并为[1,4]
4. 2. 再比较[1,4]和[3,6]：
5.    3在1-4之间，4和6相邻，合并为[1,6]
6. 最终得到：[[1,6]]

复制代码

优化解法：排序后合并

仔细想想，如果我们先把所有时间段按开始时间排序，就像把便利贴按时间顺序贴在墙上，那么我们只需要一次遍历就能完成合并。这就像你在整理行程时，先按时间排好序，然后逐个看相邻的档期能否合并。
排序合并的原理

就像理财一样：

• 先把所有区间按开始时间排序（就像把账单按日期排序）
  
• 对于每个新区间，看它是否能和当前累积的区间合并：
  
  
  
  • 如果新区间的开始时间在当前区间的结束时间之前，就应该合并（就像新的收入在之前的投资周期结束前就到了，应该一起考虑）
    
  • 如果新区间和当前区间完全分离，就把当前区间存起来，开始新的累积（就像开始一个全新的投资周期）
    
  
  

示例运行

用日程安排的例子来说明：

1. 原始日程：[[9,11], [10,12], [14,16], [15,17]]
3. 1. 排序后（已按开始时间排好）：
4.    [[9,11], [10,12], [14,16], [15,17]]
6. 2. 处理[9,11]：
7.    当前合并结果 = [[9,11]]
9. 3. 看[10,12]：
10.    10点在9-11内，可以合并
11.    当前合并结果 = [[9,12]]
13. 4. 看[14,16]：
14.    14点不在9-12内，存储之前结果，开始新区间
15.    当前合并结果 = [[9,12], [14,16]]
17. 5. 看[15,17]：
18.    15在14-16内，可以合并
19.    最终结果 = [[9,12], [14,17]]

复制代码

Java代码实现

1. public int[][] merge(int[][] intervals) {
2.     if (intervals == null || intervals.length <= 1) {
3.         return intervals;
4.     }
5.    
6.     // 按开始时间排序
7.     Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
8.    
9.     List<int[]> result = new ArrayList<>();
10.     int[] current = intervals[0];  // 当前正在处理的区间
11.    
12.     for (int i = 1; i < intervals.length; i++) {
13.         // 如果当前区间的结束时间 >= 下一个区间的开始时间，合并
14.         if (current[1] >= intervals[i][0]) {
15.             // 更新结束时间为两者中的较大值
16.             current[1] = Math.max(current[1], intervals[i][1]);
17.         } else {
18.             // 无法合并，保存当前区间，开始新区间
19.             result.add(current);
20.             current = intervals[i];
21.         }
22.     }
23.    
24.     // 别忘了最后一个区间
25.     result.add(current);
26.    
27.     return result.toArray(new int[result.size()][]);
28. }

复制代码

解法比较

让我们比较这两种方法：
暴力合并：

• 时间复杂度：O(n²)
  
• 空间复杂度：O(1)
  
• 优点：直观易懂
  
• 缺点：效率较低，特别是当区间很多时
  

排序后合并：

• 时间复杂度：O(nlogn)，主要是排序的开销
  
• 空间复杂度：O(n)，用于存储结果
  
• 优点：高效且实现简单
  
• 缺点：需要额外空间存储结果
  

实用技巧总结

解决此类区间问题的关键点：

• 考虑是否需要预处理（如排序）
  
• 注意区间的开始和结束位置
  
• 处理边界情况
  
• 别忘了最后一个区间
  

类似的问题还有：

• 会议室预订
  
• 插入区间
  
• 区间列表的交集
  

小结

通过合并区间这道题，我们学会了如何高效地处理重叠区间问题。这个技巧不仅能解决算法题，在实际工作中处理时间安排、资源分配等问题时也很有用。记住，当遇到需要处理重叠区间的问题时，先排序再合并往往是一个简单而高效的解决方案！
作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！