原文:56. 合并区间(力扣 面试题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址:https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-056/

题目:

难度:Middle

相关话题:排序数组

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

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

思路:

定义一个新数组result,用于存放更新后的所有区间。

先按照起点排序,如果当前区间的起点和上一个区间的终点存在交集,则更新上一个区间终点的位置为当前区间终点的位置;

否则,直接push当前区间。

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
  intervals.sort((a,b)=>a[0]===b[0]?a[1]-b[1]:a[0]-b[0])
  let result=[]
  for(let [x,y] of intervals){
    if(result.length===0){
      result.push([x,y])
    }else{
      let last=result[result.length-1]
      if(x>last[1]){
        result.push([x,y])
      }else{
        last[1]=Math.max(last[1],y)
      }
    }
  }
  return result
};

扩展阅读: