[leetcode]No. 56 合并区间

[liangbus]

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

示例 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] 可被视为重叠区间。

这一题 咋一看还不算特别难，但尝试写了半天，用的也还是暴力解法，转来转去还是有问题，然后看了下大神们的题解，感觉方法确实很妙啊，瞬间明白了，真的惭愧了

开始看题目给的例子，还以为是排好序的，后来发现题目根本没讲。要比较两个区间是否有交集，假如小的区间右值比大区间的左值要大（相等），便是相交。于是第一步就是选按子区间的左值进行排序，这里直接用 sort 方法即可。

初始化一个数组用来存结果，且第一个值为第一个区间，遍历从下标为1的区间开始，始终拿结果数组里面最后一个区间的右值与当前遍历的区间左值进行比较，假如相交，则更换结果集里面最后一个区间的右值；若不相交，则认为结果集从此处断开，下一次插件新的区间值，这里通过一个 id 进行控制~

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    // let curRight = 0, nextLeft = 0
    if(!intervals.length) return intervals
    intervals.sort((prev, cur) => prev[0] < cur[0] ? -1 : 1)
    const res = [intervals[0]]
    // console.log(sorted)
    let id = 0
    for(var i = 1; i < intervals.length; i++) {
        let subArr = intervals[i]
        if(subArr[0] > res[id][1]) {
            res[++id] = intervals[i]
        } else {
            res[id][1] = Math.max(subArr[1], res[id][1])
        }
    }
    return res
};