DeepSeek LeetCode 56. 合并区间 JavaScript实现

以下是 JavaScript 实现 LeetCode 56. 合并区间 的代码，包含详细注释：

/** * @param {number[][]} intervals * @return {number[][]} */varmerge=function(intervals){// 边界条件：空数组直接返回if(intervals.length===0)return[];// 按区间起点升序排序intervals.sort((a,b)=>a[0]-b[0]);// 结果数组，先放入第一个区间constmerged=[intervals[0]];// 从第二个区间开始遍历for(leti=1;i<intervals.length;i++){constcurrent=intervals[i];constlast=merged[merged.length-1];// 结果中最后一个区间// 如果当前区间起点 <= 最后一个区间的终点，说明有重叠if(current[0]<=last[1]){// 合并：更新终点为两者较大值last[1]=Math.max(last[1],current[1]);}else{// 无重叠，将当前区间加入结果merged.push(current);}}returnmerged;};

思路说明

1. 排序：按每个区间的起始值升序排序，这样所有可能重叠的区间会相邻排列。
2. 遍历合并：
   · 使用一个结果数组 merged，初始存放第一个区间。
   · 依次检查后续区间是否与 merged 的最后一个区间重叠（即当前区间起点 ≤ 最后一个区间的终点）。
   · 若重叠，则更新最后一个区间的终点为两者终点的较大值。
   · 若不重叠，则将当前区间加入 merged。
3. 返回结果。

复杂度分析

· 时间复杂度：O(n log n)，主要开销来自排序。
· 空间复杂度：O(n)，用于存储结果数组（不考虑排序的额外空间）。若考虑排序的内部空间，可能为 O(log n)。