101 lines
2.4 KiB
Markdown
101 lines
2.4 KiB
Markdown
|
||
## 题目地址
|
||
https://leetcode.com/problems/merge-intervals/description/
|
||
|
||
## 题目描述
|
||
```
|
||
Given a collection of intervals, merge all overlapping intervals.
|
||
|
||
Example 1:
|
||
|
||
Input: [[1,3],[2,6],[8,10],[15,18]]
|
||
Output: [[1,6],[8,10],[15,18]]
|
||
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
|
||
Example 2:
|
||
|
||
Input: [[1,4],[4,5]]
|
||
Output: [[1,5]]
|
||
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
|
||
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
|
||
|
||
```
|
||
|
||
## 思路
|
||
|
||
- 先对数组进行排序，排序的依据就是每一项的第一个元素的大小。
|
||
- 然后我们对数组进行遍历，遍历的时候两两运算（具体运算逻辑见下）
|
||
- 判断是否相交，如果不相交，则跳过
|
||
- 如果相交，则合并两项
|
||
## 关键点解析
|
||
|
||
- 对数组进行排序简化操作
|
||
- 如果不排序，需要借助一些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:
|
||
```Python
|
||
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
|
||
```
|
||
|
||
***复杂度分析***
|
||
- 时间复杂度：由于采用了排序，因此复杂度大概为 $O(NlogN)$
|
||
- 空间复杂度：$O(N)$
|