区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 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,4] 和 [4,5] 可被视为重叠区间。
题解
- 排序
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
let res = []
for (let i = 0; i < intervals.length; i++) { // 冒泡排序
let len = intervals.length - i - 1;
for (let j = 0; j < len; j++) {
// 比较区间的后一位，从小到大排
if (intervals[j + 1][1] < intervals[j][1]) {
let tmp = intervals[j+1];
intervals[j+1] = intervals[j];
intervals[j] = tmp;
}
}
// 比较每次冒泡的区间
if(res[0] && res[res.length-1][0] <= intervals[len][1]) { // 如果区间重叠，合并区间
res[res.length-1][0] = Math.min(res[res.length-1][0], intervals[len][0]);
} else { // 区间不重叠
res.push(intervals[len])
}
}
return res;
};
- 优化
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
let res = []; // 结果
let strat = [];
let end = [];
// 分别记录区间的开始和结束
for(let i = 0; i < intervals.length; i++) {
strat.push(intervals[i][0]);
end.push(intervals[i][1]);
}
// 排序
strat.sort((a, b) => a - b);
end.sort((a, b) => a - b);
// 合并区间，i为区间的结束，j为区间的开始
for(let i = 0, j = 0; i < intervals.length; i++) {
// 找到合并的边界，记录不可再合并的区间
if(i == intervals.length - 1 || strat[i+1] > end[i]) {
res.push([strat[j], end[i]]);
j = i + 1;
}
}
return res;
};
