56. 合并区间

[mengjian-github]

以数组 intervals 表示若干个区间的集合，其中单个区间为 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] 可被视为重叠区间。

[mengjian-github]

这道题暴力求解有点复杂，关键点在于排序，排序之后，只需要比较b1和a2的关系，就可以区分出来是否应该合并了：

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    const result = [];
    intervals.sort((a, b) => {
        return a[0] - b[0];
    });
    for (const interval of intervals) {
        if (result.length === 0) {
            result.push(interval);
        } else {
            const [a1, b1] = result[result.length - 1];
            const [a2, b2] = interval;
            if (a2 > b1) {
                result.push(interval);
            } else {
                result[result.length - 1] = [a1, Math.max(b1, b2)];
            }
        }
    }
    return result;
};