【忍者算法】从日程安排到区间合并：探索合并区间问题｜LeetCode 56 合并区间
从日程安排到区间合并：探索合并区间问题生活中的算法
想象你是一位活动策划师，桌上摆着许多便利贴，每张写着不同的活动时间段：9:00-11:00的晨会、10:30-12:00的培训、14:00-16:00的项目汇报、15:00-17:00的团队建设...有些活动时间明显重叠了，为了让日程更清晰，你需要将这些重叠的时间段合并起来。比如晨会和培训重叠了，就可以合并为9:00-12:00的一个大时间段。
这种情况在生活中随处可见。比如医院的预约时段合并、健身房的预定时间优化、公司会议室的档期管理，甚至是地铁维修时段的规划等。
问题描述
LeetCode第56题"合并区间"是这样描述的：给出一个区间的集合，请合并所有重叠的区间。
例如：
输入：intervals = [,,,]
输出：[,,]
解释：区间 和 重叠，将它们合并为 最直观的解法：暴力合并
就像你整理日程表一样，最直观的方法是：拿起每张便利贴，和其他所有便利贴比较，看看能否合并。
让我们用一个简单的例子来理解：
时间段：[, , ]
1. 比较和：
2在1-4之间，合并为
2. 再比较和：
3在1-4之间，4和6相邻，合并为
最终得到：[]优化解法：排序后合并
仔细想想，如果我们先把所有时间段按开始时间排序，就像把便利贴按时间顺序贴在墙上，那么我们只需要一次遍历就能完成合并。这就像你在整理行程时，先按时间排好序，然后逐个看相邻的档期能否合并。
排序合并的原理
就像理财一样：
[*]先把所有区间按开始时间排序（就像把账单按日期排序）
[*]对于每个新区间，看它是否能和当前累积的区间合并：
[*]如果新区间的开始时间在当前区间的结束时间之前，就应该合并（就像新的收入在之前的投资周期结束前就到了，应该一起考虑）
[*]如果新区间和当前区间完全分离，就把当前区间存起来，开始新的累积（就像开始一个全新的投资周期）
示例运行
用日程安排的例子来说明：
原始日程：[, , , ]
1. 排序后（已按开始时间排好）：
[, , , ]
2. 处理：
当前合并结果 = []
3. 看：
10点在9-11内，可以合并
当前合并结果 = []
4. 看：
14点不在9-12内，存储之前结果，开始新区间
当前合并结果 = [, ]
5. 看：
15在14-16内，可以合并
最终结果 = [, ]Java代码实现
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1) {
return intervals;
}
// 按开始时间排序
Arrays.sort(intervals, (a, b) -> a - b);
List<int[]> result = new ArrayList<>();
int[] current = intervals;// 当前正在处理的区间
for (int i = 1; i < intervals.length; i++) {
// 如果当前区间的结束时间 >= 下一个区间的开始时间，合并
if (current >= intervals) {
// 更新结束时间为两者中的较大值
current = Math.max(current, intervals);
} else {
// 无法合并，保存当前区间，开始新区间
result.add(current);
current = intervals;
}
}
// 别忘了最后一个区间
result.add(current);
return result.toArray(new int[]);
}解法比较
让我们比较这两种方法：
暴力合并：
[*]时间复杂度：O(n²)
[*]空间复杂度：O(1)
[*]优点：直观易懂
[*]缺点：效率较低，特别是当区间很多时
排序后合并：
[*]时间复杂度：O(nlogn)，主要是排序的开销
[*]空间复杂度：O(n)，用于存储结果
[*]优点：高效且实现简单
[*]缺点：需要额外空间存储结果
实用技巧总结
解决此类区间问题的关键点：
[*]考虑是否需要预处理（如排序）
[*]注意区间的开始和结束位置
[*]处理边界情况
[*]别忘了最后一个区间
类似的问题还有：
[*]会议室预订
[*]插入区间
[*]区间列表的交集
小结
通过合并区间这道题，我们学会了如何高效地处理重叠区间问题。这个技巧不仅能解决算法题，在实际工作中处理时间安排、资源分配等问题时也很有用。记住，当遇到需要处理重叠区间的问题时，先排序再合并往往是一个简单而高效的解决方案！
作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]