# 0056. 合并区间

### 题目地址(56. 合并区间)

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

### 题目描述

```
给出一个区间的集合，请合并所有重叠的区间。

 

示例 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] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

 

提示：

intervals[i][0] <= intervals[i][1]

```

### 前置知识

* 排序

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

* 先对数组进行排序，排序的依据就是每一项的第一个元素的大小。
* 然后我们对数组进行遍历，遍历的时候两两运算（具体运算逻辑见下）
* 判断是否相交，如果不相交，则跳过
* 如果相交，则合并两项

### 关键点解析

* 对数组进行排序简化操作
* 如果不排序，需要借助一些 hack,这里不介绍了

### 代码

* 语言支持: Javascript，Python3

```js
/*
 * @lc app=leetcode id=56 lang=javascript
 *
 * [56] Merge Intervals
 */
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */

function intersected(a, b) {
  if (a[0] > b[1] || a[1] < b[0]) return false;
  return true;
}

function mergeTwo(a, b) {
  return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
}
var merge = function (intervals) {
  // 这种算法需要先排序
  intervals.sort((a, b) => a[0] - b[0]);
  for (let i = 0; i < intervals.length - 1; i++) {
    const cur = intervals[i];
    const next = intervals[i + 1];

    if (intersected(cur, next)) {
      intervals[i] = undefined;
      intervals[i + 1] = mergeTwo(cur, next);
    }
  }
  return intervals.filter((q) => q);
};
```

Python3 Code:

```
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        """先排序，后合并"""
        if len(intervals) <= 1:
            return intervals

        # 排序
        def get_first(a_list):
            return a_list[0]
        intervals.sort(key=get_first)

        # 合并
        res = [intervals[0]]
        for i in range(1, len(intervals)):
            if intervals[i][0] <= res[-1][1]:
                res[-1] = [res[-1][0], max(res[-1][1], intervals[i][1])]
            else:
                res.append(intervals[i])

        return res
```

***复杂度分析***

令 n 为 intervals 的长度。

* 时间复杂度：由于采用了排序，因此复杂度大概为 $O(nlogn)$
* 空间复杂度：$O(n)$

### 扩展

这道题是让你合并区间。这里还有一道删除区间的题目，大家可以结合起来练习 [Interval-Carving](https://binarysearch.com/problems/Interval-Carving)。

参考 Python3 代码：

```py
class Solution:
    def solve(self, intervals, cut):
        ans = []
        for s, e in intervals:
            if s < cut[0]: ans.append([s, min(e, cut[0])])
            if cut[1] < e: ans.append([max(s, cut[1]), e])
        return ans
```

另外下面的图是我思考时候的草图，红色表示需要删除的区间，灰色是题目给的区间。

![](https://p.ipic.vip/exqstp.jpg)

> 注意是 if 不是 else if 。 否则的话，你的判断会很多。

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/laky7s.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/56.merge-intervals.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.