【每日算法】 LeetCode 56. 合并区间-洪萨配资

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 56. 合并区间

1. 题目描述

1.1 问题陈述

给定一个区间的集合intervals，其中每个区间表示为[start, end]，你需要合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需覆盖输入中的所有区间。

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

注意：输入类型可能为数组或类似结构，输出要求有序（通常按起始点升序）。作为前端开发者，你需处理类似数组操作和数据格式化问题。

2. 问题分析

2.1 输入输出分析

输入：一个二维数组intervals，每个子数组表示一个区间，包含起始点start和结束点end。假设start <= end，且数组可能无序。
输出：一个二维数组，包含合并后的不重叠区间，按起始点升序排列。
重叠定义：两个区间[a, b]和[c, d]重叠，如果a <= d且c <= b（即一个区间的起始点小于或等于另一个区间的结束点）。合并后新区间为[min(a, c), max(b, d)]。

2.2 关键点

前端场景中，这类问题常见于日历事件合并、时间轴渲染或数据可视化（如甘特图），其中需优化重叠元素的显示。
核心挑战是高效识别和处理重叠区间，避免 O(n²) 的暴力比较，以提升性能。

3. 解题思路

3.1 思路一：排序后合并（最优解）

步骤：
1. 将区间按起始点start升序排序。
2. 初始化结果数组merged，遍历排序后的区间：
  - 如果merged为空或当前区间与merged中最后一个区间不重叠（即当前区间的起始点大于最后一个区间的结束点），则将当前区间添加到merged。
  - 否则，合并区间：更新merged最后一个区间的结束点为当前区间结束点与最后一个区间结束点的最大值。
复杂度：时间复杂度 O(n log n)（主要来自排序），空间复杂度 O(log n)（排序使用的栈空间，或 O(n) 如果存储结果）。这是最优解，因为排序是必要步骤，且后续线性扫描高效。
前端关联：类似前端中对事件列表按时间排序后渲染，减少重复计算。

3.2 思路二：暴力法

步骤：遍历每个区间，与其他所有区间比较，合并重叠区间，重复直到无重叠。效率低，仅适用于小数据集或作为理解基础。
复杂度：时间复杂度 O(n²)，空间复杂度 O(n)。不推荐用于生产环境。

4. 各思路代码实现

以下用 JavaScript 实现，作为前端开发者的常用语言。

4.1 思路一：排序后合并的 JavaScript 实现

/** * @param {number[][]} intervals * @return {number[][]} */varmerge=function(intervals){if(intervals.length===0)return[];// 按起始点升序排序intervals.sort((a,b)=>a[0]-b[0]);constmerged=[];for(letintervalofintervals){// 如果 merged 为空或当前区间不重叠if(merged.length===0||merged[merged.length-1][1]<interval[0]){merged.push(interval);}else{// 合并区间：更新最后一个区间的结束点merged[merged.length-1][1]=Math.max(merged[merged.length-1][1],interval[1]);}}returnmerged;};// 测试示例console.log(merge([[1,3],[2,6],[8,10],[15,18]]));// 输出 [[1,6],[8,10],[15,18]]console.log(merge([[1,4],[4,5]]));// 输出 [[1,5]]

4.2 思路二：暴力法的 JavaScript 实现（仅作参考）

/** * 暴力法实现合并区间 * @param {number[][]} intervals * @return {number[][]} */varmergeBruteForce=function(intervals){if(intervals.length===0)return[];letmerged=[...intervals];letchanged=true;// 重复合并直到无变化while(changed){changed=false;constnewMerged=[];for(leti=0;i<merged.length;i++){letcurrent=merged[i];letisMerged=false;for(letj=0;j<newMerged.length;j++){// 检查重叠if(current[0]<=newMerged[j][1]&&newMerged[j][0]<=current[1]){// 合并区间newMerged[j][0]=Math.min(newMerged[j][0],current[0]);newMerged[j][1]=Math.max(newMerged[j][1],current[1]);isMerged=true;changed=true;break;}}if(!isMerged){newMerged.push(current);}}merged=newMerged;}returnmerged.sort((a,b)=>a[0]-b[0]);// 确保输出有序};// 注意：暴力法效率低，仅用于小数据测试console.log(mergeBruteForce([[1,3],[2,6],[8,10],[15,18]]));// 输出类似结果

5. 各实现思路的复杂度、优缺点对比表格

思路	时间复杂度	空间复杂度	优点	缺点	适用场景
排序后合并	O(n log n)	O(log n) 或 O(n)	高效，代码简洁，易于维护	依赖排序，可能修改原数组	大多数前端应用，如事件合并、数据可视化
暴力法	O(n²)	O(n)	实现简单，易于理解	效率低，不适用于大数据	小数据集学习或原型开发