第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0056. 合并区间

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

题目描述

1
给出一个区间的集合,请合并所有重叠的区间。
2
3
4
5
示例 1:
6
7
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
8
输出: [[1,6],[8,10],[15,18]]
9
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
10
示例 2:
11
12
输入: intervals = [[1,4],[4,5]]
13
输出: [[1,5]]
14
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
15
注意:输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
16
17
18
19
提示:
20
21
intervals[i][0] <= intervals[i][1]
Copied!

前置知识

  • 排序

公司

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

思路

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

关键点解析

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

代码

  • 语言支持: Javascript,Python3
1
/*
2
* @lc app=leetcode id=56 lang=javascript
3
*
4
* [56] Merge Intervals
5
*/
6
/**
7
* @param {number[][]} intervals
8
* @return {number[][]}
9
*/
10
11
function intersected(a, b) {
12
if (a[0] > b[1] || a[1] < b[0]) return false;
13
return true;
14
}
15
16
function mergeTwo(a, b) {
17
return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
18
}
19
var merge = function (intervals) {
20
// 这种算法需要先排序
21
intervals.sort((a, b) => a[0] - b[0]);
22
for (let i = 0; i < intervals.length - 1; i++) {
23
const cur = intervals[i];
24
const next = intervals[i + 1];
25
26
if (intersected(cur, next)) {
27
intervals[i] = undefined;
28
intervals[i + 1] = mergeTwo(cur, next);
29
}
30
}
31
return intervals.filter((q) => q);
32
};
Copied!
Python3 Code:
1
class Solution:
2
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
3
"""先排序,后合并"""
4
if len(intervals) <= 1:
5
return intervals
6
7
# 排序
8
def get_first(a_list):
9
return a_list[0]
10
intervals.sort(key=get_first)
11
12
# 合并
13
res = [intervals[0]]
14
for i in range(1, len(intervals)):
15
if intervals[i][0] <= res[-1][1]:
16
res[-1] = [res[-1][0], max(res[-1][1], intervals[i][1])]
17
else:
18
res.append(intervals[i])
19
20
return res
Copied!
复杂度分析
令 n 为 intervals 的长度。
  • 时间复杂度:由于采用了排序,因此复杂度大概为 $O(nlogn)$
  • 空间复杂度:$O(n)$

扩展

这道题是让你合并区间。这里还有一道删除区间的题目,大家可以结合起来练习 Interval-Carving
参考 Python3 代码:
1
class Solution:
2
def solve(self, intervals, cut):
3
ans = []
4
for s, e in intervals:
5
if s < cut[0]: ans.append([s, min(e, cut[0])])
6
if cut[1] < e: ans.append([max(s, cut[1]), e])
7
return ans
Copied!
另外下面的图是我思考时候的草图,红色表示需要删除的区间,灰色是题目给的区间。
注意是 if 不是 else if 。 否则的话,你的判断会很多。
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。