Skip to content

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]]);
};



回到顶部