一、题目内容 中等

以数组 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] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

    二、解题思路

    大家应该都感觉到了，此题一定要排序，那么按照左边界排序，还是右边界排序呢？
    都可以！
    那么我按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
    局部最优可以推出全局最优，找不出反例，试试贪心。
    image.png

    三、具体代码

    1. /**
    2. * @param {number[][]} intervals
    3. * @return {number[][]}
    4. */
    5. var merge = function (intervals) {
    6. intervals.sort((a, b) => a[0] - b[0])
    7. const result = []
    8. let [left, right] = intervals[0]
    9. for (let i = 1, len = intervals.length; i < len; i++) {
    10.   const [a, b] = intervals[i]
    11.   if (a <= right) right = Math.max(right, b)
    12.   else {
    13.     result.push([left, right])
    14.     left = a
    15.     right = b
    16.   }
    17. }
    18. result.push([left, right])
    19. return result
    20. };

    四、其他解法