0056._Merge_Intervals

发表于 分类于 ， ，

056. Merge Intervals

难度: Medium

刷题内容

原题连接

内容描述

给出一个区间的集合，请合并所有重叠的区间。

示例 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)**

先对输入进行排序，然后判断是存在间隔

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @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]]);
};