0056.合并区间
难度：🟡 中等
标签：数组、排序
链接：56. 合并区间
题目描述
以数组 intervals 表示若干个区间的集合，其中 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[1,5](./1,5.md)
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
解题思路
核心思想
本题的核心是识别并合并所有重叠的区间。一个关键的洞察是，如果我们将所有区间按照起始位置进行排序，那么我们只需要依次比较相邻（或已合并的最后一个）区间即可。
思路选择
排序 + 贪心法 是解决此问题的标准最优思路。
我们首先将所有区间按照其起始值
start_i进行升序排序。然后，我们维护一个结果数组
merged，并将第一个区间放入其中。接着，我们遍历剩余的区间。对于每一个当前区间
current，我们将其与merged中的最后一个区间last进行比较：如果
current的起始值大于last的结束值 (current.start > last.end)，说明它们不重叠，直接将current加入merged。如果
current的起始值小于等于last的结束值，说明它们重叠。我们需要合并这两个区间，合并后的新区间的结束值是max(last.end, current.end)。我们只需更新last的结束值即可。
关键步骤
处理边界情况：如果区间数组长度小于等于 1，无需合并，直接返回。
排序：按照每个区间的起始位置对
intervals数组进行升序排序。初始化：创建一个结果数组
merged，并将排序后的第一个区间intervals[0]添加进去。循环遍历：从第二个区间开始遍历排序后的数组。 a. 取出
merged中的最后一个区间last。 b. 取出当前遍历到的区间current。 c. 判断重叠：如果current[0] <= last[1]，则两个区间重叠。更新last[1]为Math.max(last[1], current[1])。 d. 不重叠：如果current[0] > last[1]，则两个区间不重叠。将current直接推入merged数组。返回结果：遍历结束后，
merged中就是所有合并后的不重叠区间。
代码实现 (推荐)
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
if (intervals.length <= 1) {
return intervals;
}
// 1. 按区间的起始位置排序
intervals.sort((a, b) => a[0] - b[0]);
// 2. 初始化结果数组，放入第一个区间
const merged = [intervals[0]];
// 3. 遍历剩余区间
for (let i = 1; i < intervals.length; i++) {
const lastMerged = merged[merged.length - 1];
const currentInterval = intervals[i];
// 4. 判断是否重叠
if (currentInterval[0] <= lastMerged[1]) {
// 重叠，更新最后一个合并区间的结束位置
lastMerged[1] = Math.max(lastMerged[1], currentInterval[1]);
} else {
// 不重叠，直接添加新区间
merged.push(currentInterval);
}
}
return merged;
};
原始代码分析 (用户提供)
您提供的代码是此问题的标准且高效的解法，逻辑完全正确。
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function (intervals) {
if (intervals.length === 0) return [];
// 1. 排序，关键步骤
intervals.sort((a, b) => a[0] - b[0]);
// 2. 初始化结果
let results = [intervals[0]]
// 3. 遍历并比较
for (let i = 1; i < intervals.length; i++) {
const [targetStart, targetEnd] = results[results.length - 1];
const [curStart, curEnd] = intervals[i];
// 如果不重叠，直接推入
if (curStart > targetEnd) {
results.push(intervals[i]);
}
// 如果重叠，只在需要时更新结束边界
else if (curEnd > targetEnd) {
results[results.length - 1][1] = curEnd;
}
}
return results;
};
优点：此实现堪称模板，正确地实现了排序和单次遍历合并的逻辑。变量解构赋值
[start, end]让代码更易读。代码风格: 代码非常清晰，逻辑分支明确，是一个优秀的实现。
复杂度分析
时间复杂度：O(n log n) 其中 n 是区间的数量。时间主要消耗在排序上。排序后，我们只需要对区间进行一次线性扫描，其时间为 O(n)。
空间复杂度：O(log n) 或 O(n) 不考虑存储结果的数组，空间复杂度主要取决于排序算法在递归时所需的栈空间。
相关题目
总结
本题是区间问题中的一个经典类型。通过“先排序，再合并”的策略，可以将一个看似复杂的问题转化为简单的线性扫描。排序是解决大多数区间问题的关键预处理步骤。