题目链接

https://leetcode-cn.com/problems/merge-intervals/

题目描述

以数组 intervals 表示若干个区间的集合,其中单个区间为 $intervals[i] = [start_i, end_i]$。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。

示例

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

题解

假设区间的起点是无序的,在对比区间右端点和另一个区间的左端点时,可能会出现本应该合并的区间因为对比顺序的错误而导致矛盾,所以区间一定是要按照左端点或者右端点的其中一个值进行有序排列的。

如果按照区间的左端点升序排序,那么在排序完的列表中,可以合并的区间一定是连续的,如下图:


左端点排序
左端点排序


因此在合并区间之前应该优先进行排序,我们默认使用快排,时间复杂度是 $O(nlogn)$,空间复杂度为 $O(1)$。在排序后的基础上只需要进行一次线性遍历就可以完成合并的处理,代码如下:

const merge = (intervals) => {
  const result = [];

  if (intervals.length > 0) {
    intervals.sort((a, b) => a[0] - b[0]);
    let prev = intervals[0];

    for (let i = 1; i < intervals.length; i++) {
      const cur = intervals[i];

      if (prev[1] >= cur[0]) {
        prev[1] = Math.max(prev[1], cur[1]);
      } else {
        result.push(prev);
        prev = cur;
      }
    }

    result.push(prev);
  }

  return result;
}

复杂度分析:

  • 时间复杂度:$O(nlogn) + O(n) = O(nlogn)$
  • 空间复杂度:$O(1) + O(1) = O(1)$