## 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.

## Solutions

合并不同的区间。

### 1. Sort

# Time: O(nlogn)
# Space: O(n)
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
res = []
intervals = sorted(intervals, key=lambda x: x[0])

for item in intervals:
if res and item[0] <= res[-1][1]:
# res[-1][1] = item[1]
res[-1][1] = max(res[-1][1], item[1])
else:
res.append(item)
return res
# 169/169 cases passed (104 ms)
# Your runtime beats 18.37 % of python3 submissions
# Your memory usage beats 6.52 % of python3 submissions (14.8 MB)


注意 for 循环中注释哪一样容易缺！