056. Merge Intervals
难度: Medium
刷题内容
原题连接
- https://leetcode-cn.com/problems/merge-intervals/
内容描述
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
解题方案
思路 1 **- 时间复杂度: O(2N)*- 空间复杂度: O(N)***
先对输入进行排序，然后判断是存在间隔
代码：
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
if (!intervals || !intervals.length) {
return intervals;
}
intervals.sort((a, b) => (a[0] - b[0]))
return intervals.reduce((acc, [ currentLeft, currentRight ]) => {
if (currentLeft > acc[acc.length - 1][1]) {
acc.push([ currentLeft, currentRight ]);
} else if (currentRight > acc[acc.length - 1][1]){
acc[acc.length - 1][1] = currentRight;
}
return acc;
}, [intervals[0]]);
};
