贪心算法专题(十四)：万流归宗——「合并区间」-洪萨配资

哈喽各位，我是前端L。

欢迎来到贪心算法专题第十四篇！

题目很简单：给你一堆乱序的区间，比如 [1,3], [8,10], [2,6], [15,18]。

请你把重叠的区间合并。

[1,3]和[2,6]重叠，合并后变成[1,6]（取最小起点，最大终点）。
[8,10]和[15,18]没人理它们，保持原样。
最终输出：[[1,6], [8,10], [15,18]]。

力扣 56. 合并区间

https://leetcode.cn/problems/merge-intervals/

题目分析：

输入：intervals数组。
输出：合并后的数组。

核心思维：排序 + 动态更新右边界

依然是老套路：先按 Start 排序。

排序后：[1,3], [2,6], [8,10], [15,18]。

贪心策略：

我们将第一个区间放入结果集 result 中作为**“当前正在合并的区间”**。

然后遍历后面的区间：

重叠了？(当前.start <= 结果集中最后一个.end)
- 不需要新增区间。
- 合并操作：我们要把结果集里那个区间的右边界撑大。
- 新的右边界 =Math.max(结果集.end, 当前.end)。
- 注意：这里取 Max，因为我们要尽可能包含更多的范围（合并）。这与“射气球”取 Min（找交集）正好相反。
没重叠？
- 说明当前结果集里的那个区间已经合并完毕，无法再向后延伸了。
- 直接把当前区间 push 进结果集，作为新的“正在合并对象”。

算法流程 (JavaScript)

特判：长度为 0 或 1 直接返回。
排序：intervals.sort((a, b) => a[0] - b[0])。
初始化：result = [intervals[0]]。
遍历：从i = 1开始。
- 取出result的最后一个元素last。
- 取出当前遍历元素cur。
- 如果cur[0] <= last[1](有重叠)：
  - last[1] = Math.max(last[1], cur[1])（直接修改 result 里的元素）。
- 否则：
  - result.push(cur)。
返回result。

代码实现

JavaScript

/** * @param {number[][]} intervals * @return {number[][]} */ var merge = function(intervals) { if (intervals.length === 0) return []; // 1. 按左边界从小到大排序 intervals.sort((a, b) => a[0] - b[0]); // 初始化结果集，先把第一个放进去 const result = [intervals[0]]; // 2. 从第二个开始遍历 for (let i = 1; i < intervals.length; i++) { let cur = intervals[i]; // 获取结果集中“当前正在合并”的那个区间（也就是最后一个） let last = result[result.length - 1]; // 判断是否重叠 // 当前区间的左边界 <= 上一个区间的右边界 if (cur[0] <= last[1]) { // 发现重叠！执行合并 // 只需要更新右边界，左边界肯定是用 last[0] (因为它更小，排序保证的) // 右边界要取两者中最大的，这样才能包住两个区间 last[1] = Math.max(last[1], cur[1]); } else { // 没有重叠，直接放入结果集 result.push(cur); } } return result; };

深度辨析：区间三兄弟总结

这三道题（452射气球, 435无重叠, 56合并）是区间问题的“三驾马车”。它们的第一步永远是Sort by Start。

区别在于处理重叠时的贪心决策：

题目	目标	重叠时的操作	边界更新策略
452. 射气球	找公共交集	箭数不变，范围变小	`end = Math.min`(取交集)
435. 无重叠	丢弃区间	移除数+1，保留短的	`end = Math.min`(为了不挡路)
56. 合并区间	融合区间	区间数不变，范围变大	`end = Math.max`(取并集)