Merge Intervals | 合并区间

Merge Intervals | 合并区间

“合并区间”(Merge Intervals)通常是这样的：给定一个区间列表,其中每个区间由一对整数表示 [start, end],你需要合并所有重叠的区间,并返回一个不重叠的区间列表.

1. 实现

   function merge(intervals: number[][]): number[][] {
       if (intervals.length === 0) return [];
       
       // 1. 按照每个区间的开始值排序
       intervals.sort((a, b) => a[0] - b[0]);
       
       // 2. 初始化结果数组
       const result: number[][] = [intervals[0]];
       
       // 3. 遍历区间并合并
       for (let i = 1; i < intervals.length; i++) {
           const lastInterval = result[result.length - 1];
           const currentInterval = intervals[i];
           
           // 如果当前区间和最后一个区间重叠,合并
           if (currentInterval[0] <= lastInterval[1]) {
               lastInterval[1] = Math.max(lastInterval[1], currentInterval[1]);
           } else {
               // 否则,直接将当前区间加入结果
               result.push(currentInterval);
           }
       }
       
       return result;
   }
   

2. 实现说明

   1. 排序：首先对区间按起始位置升序排序,这样可以保证重叠的区间会相邻.
   2. 合并逻辑：遍历排序后的区间,判断当前区间是否与结果数组中的最后一个区间重叠.如果重叠,则更新最后一个区间的结束值,否则直接添加当前区间.

3. 这种方法的时间复杂度是 O(n log n),因为排序是最耗时的部分,n 是区间的数量.