LeetCode 「中等」56.合并区间
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
解答
具体步骤
- 排序区间
- 将所有区间按照起始位置进行排序。这样可以让相邻的区间更容易判断是否重叠
- 初始化结果数组
- 创建一个空数组
result，用于存储合并后的区间 - 将排序后的第一个区间直接加入
result，作为当前区间
- 遍历区间
- 从第二个区间开始遍历排序后的区间列表
- 对于每个区间，检查它是否与
result中的最后一个区间重叠：- 如果当前区间的起始位置 <=
result中最后一个区间的结束位置，说明两个区间重叠，需要合并 - 合并的方式是更新
result中的最后一个区间的结束位置为max(result[result.length - 1][1], 当前区间的结束位置) - 如果当前区间不与
result中的最后一个区间重叠，则直接将当前区间加入result
- 如果当前区间的起始位置 <=
- 返回结果
Code
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
if (intervals.length < 2) return intervals;
// 按起始位置排序
intervals.sort((a, b) => a[0] - b[0]);
// 初始化结果数组
const result = [intervals[0]];
// 遍历区间
for (let i = 1; i < intervals.length; ++i) {
const currentInterval = intervals[i];
// 缓存最后一个区间
const lastInterval = result[result.length - 1];
// 检查是否重叠
if (currentInterval[0] <= lastInterval[1]) {
// 合并区间
lastInterval[1] = Math.max(currentInterval[1], lastInterval[1]);
} else {
// 不重叠，直接加入结果
result.push(currentInterval);
}
}
return result;
};