[56] 合并区间

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

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

提示：

intervals[i][0] <= intervals[i][1]

解区间的题型最重要的就是处理区间之间顺序关系，这能让我们思考逻辑时直接砍掉一半的逻辑节点，对于思考复杂树的难度是指数级下降的。

比如对于本题来说，我们只需要让区间的某一边有序（其实起始位置或结束位置有序都行，下面的解法对起始位置排序）。

这样一来我们对两个区间取并集时，起始位置就一定会取第一个区间的。之后只需要比较第二个区间的起始位置与第一个区间的结束位置，就能知道两个区间是否相交了。这样是新建一个区间还是扩展一个区间的选择就非常好做了。

所以解区间问题的关键点在于优先排序。

function merge(intervals: number[][]): number[][] {
  const res: number[][] = [];
  intervals.sort((a, b) => a[0] - b[0]);

  for (const interval of intervals) {
    const origin = res[res.length - 1];
    if (res.length <= 0 || origin[1] < interval[0]) {
      // 不存在交集时直接放入
      res.push(interval);
    } else {
      // 此时存在交集，确认是包含还是交集关系，取代原来的最后一个区间
      res[res.length - 1][1] = Math.max(origin[1], interval[1]);
    }
  }

  return res;
}