# NC37.合并区间

# 题目描述 (opens new window)

TIP

知识点：排序、数组

TIP

关联企业：酷家乐、腾讯、美团、字节跳动

# 算法思路

我们可以先使用排序的方式将这个二维数组内部的子数组是有顺序的，我们按照区间的左端点进行排序，那么在排完序的数组中，可以合并的区间一定是连续的。

这里定义一个变量res，用来存储最终的结果返回。

首先，我们将列表中的区间按照左端点升序排列，然后我们将第一个区间加入 merged 数组, 并按照顺序依次考虑之后的每个区间。

如果当前区间的左端点在数组merged中最后一个区间的右端点之后，那么他们不会重合，我们可以直接将这个区间加入数组merged的末尾。
否则，它们重合，我们需要用当前区间的右端点更新数组merged中最后一个区间的右端点，将其置为二者的较大值。

function merge(intervals) {
  // 如果传递进来的数组长度为0 返回一个空数组
  if (intervals.length === 0) {
    return [];
  }
  // 创建合并数组
  let res = [];
  // 将数组进行升序排序
  intervals.sort(function (a, b) {
    return a.start - b.start;
  });

  // console.log(intervals)
  // 结果数组放进第一个数组 [ Interval { start: 10, end: 30 } ] 是这种形式
  res.push(intervals[0]);

  console.log(res);
  // 从原数组的第一个元素进行遍历
  for (let i = 1; i < intervals.length; i++) {
    // 如果当前区间的左端点 大于res数组最后一个元素的右端点
    // 这个时候是没有交集的 此时直接将当前这个数组放进结果集
    if (intervals[i].start > res[res.length - 1].end) {
      res.push(intervals[i]);
    } else {
      // 说明区间有交集
      // 如果当前区间的右端点
      if (intervals[i].end > res[res.length - 1].end) {
        // 更新右端点为最大值
        res[res.length - 1].end = intervals[i].end;
      }
    }
  }
  return res;
}
module.exports = {
  merge: merge,
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

这道题目在牛客上在访问数组元素的时候，使用的是start和end这个属性，在力扣上使用的是索引，这点要尤其注意

# 复杂度分析

时间复杂度：O(nlogn)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 OO(nlogn)。
空间复杂度：O(logn)，其中 n为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn) 即为排序所需要的空间复杂度。