题目

题目来源：力扣（LeetCode）

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

思路分析

我们按照区间的左端点进行升序排序，那么在拍完序的列表中，可以合并的区间一定是连续的。如下图所示，标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间，它们在排完序的列表中是连续的：
image.png
我们定义一个 merged 数组来存储最终的答案。

首先，我们将列表中的区间按照左端点进行升序排序，然后将排序后的第一个区间放入 merged 数组中，然后遍历排序后的数组，判断当前遍历的区间：

  • 如果当前区间的左端点 大于 merged数组中最后一个元素的右端点，说明当前区间和前面的区间不会重合，将当前区间放入 merged数组中
  • 当前区间的左端点 小于 merged 数组中最后一个元素的右端点，说明当前区间有交集，则需要合并两个区间，此时判断当前区间的右端点是否大于 merged 数组中最后一个元素的右端点
  • 当前区间的右端点 大于 merged 数组中最后一个元素的右端点，则将 merged数组中最后一个元素的右端点更新为当前区间的右端点
  1. /**
  2.  * @param {number[][]} intervals
  3.  * @return {number[][]}
  4.  */
  5. var merge = function(intervals) {
  6.   // 如果传递进来的数组长度为 0，则返回一个空数组
  7.   if (!intervals.length) {
  8.     return []
  9.   }
  10.   // 用数组 merged 存储最终的答案
  11.   const merged = [];
  12.   // 将数组按照区间的左端点进行升序排序
  13.   intervals.sort((a, b) => a[0] - b[0]);
  15.   // 将排序后的数组的第一个区间放入结果中
  16.   merged.push(intervals[0]);
  18.   // 从原数组的第一个元素开始遍历
  19.   for (let i = 1; i < intervals.length; i++) {
  20.     // 如果当前区间的左端点 大于 merged数组中最后一个元素的右端点
  21.     // 说明当前区间和前面的区间不会重合，将当前区间放入 merged数组中
  22.     if (intervals[i][0] > merged[merged.length - 1][1]) {
  23.       merged.push(intervals[i])
  24.     } else { // 当前区间的左端点 小于 merged 数组中最后一个元素的右端点，说明当前区间有交集
  25.       // 两个区间有交集，则需要合并两个区间，此时判断判断当前区间的右端点是否 大于 merged 数组中最后一个元素的右端点
  26.       if (intervals[i][1] > merged[merged.length -1][1]) {
  27.         // 当前区间的右端点 大于 merged 数组中最后一个元素的右端点
  28.         // 则将 merged数组中最后一个元素的右端点更新为当前区间的右端点
  29.         merged[merged.length - 1][1] = intervals[i][1]
  30.       }
  31.     }
  32.   }
  34.   return merged
  36. };