1. 题目描述

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

示例 1:

  1. 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
  2. 输出: [[1,6],[8,10],[15,18]]
  3. 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

  1. 输入: intervals = [[1,4],[4,5]]
  2. 输出: [[1,5]]
  3. 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示：

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

2. 实现思路

这个题目的思路就是直接遍历数组，然后按照条件进行合并，合并的过程如下：

  • 首先，按照每一个数组的第一项的大小进行升序排序
  • 当后一项的左边界小于等于前一项的右边界的时候，就可以进行合并
  • 合并的时候，只需要将后一项的边界编程前一项的边界就可以了
  • 需要注意的是，有可能后一项的右边界比前一项的右边界小，那右边界还是前一项的右边界
  • 重复上述过程，直至遍历完所有的数组

该方法的时间复杂度为O(n)，空间复杂度为O(n)。

3. 代码实现

  1. /**
  2.  * @param {number[][]} intervals
  3.  * @return {number[][]}
  4.  */
  5. var merge = function(intervals) {
  6.     if(intervals.length === 0) {
  7.         return []
  8.     }
  9.     let res = []
  10.     intervals.sort((a, b) => a[0] - b[0])
  11.     res.push(intervals[0])
  13.     for(let i = 1; i < intervals.length; i++){
  14.         // 如果当前项的第一个数字比前一项的第二个数字大，就直接将当前数组放到结果中
  15.         if(intervals[i][0] > res[res.length - 1][1]){
  16.             res.push(intervals[i])
  17.         } else {  
  18.             // 如果当前项的第一个数字比前一项的第二个数字小，并且当前项的第二个数字比前一项的第二个数字大，就将上一项的第二个数字换成当前项的第二项
  19.             if(intervals[i][1] > res[res.length - 1][1]){
  20.                 res[res.length - 1][1] = intervals[i][1]
  21.             }
  22.         }
  23.     }
  24.     return res
  25. };

4. 提交结果

56. 合并区间 - 图1