0. 链接
1. 题目
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.
2. 思路1:先按照左端点排序+再逐个合并区间
- 按照各个区间左端值升序排列,再从左到右合并两个相邻区间,遇到不能合并的,则收集到结果里;否则修改区间右端点值
3. 代码
# coding:utf8
from typing import List
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) <= 1:
return intervals
intervals.sort(key=lambda x: x[0], reverse=False)
last_idx = 0
for i in range(1, len(intervals)):
last_interval = intervals[last_idx]
interval = intervals[i]
if interval[0] <= last_interval[1] <= interval[1]:
last_interval[1] = interval[1]
elif last_interval[1] < interval[0]:
last_idx += 1
last_interval = intervals[last_idx]
last_interval[0] = interval[0]
last_interval[1] = interval[1]
return intervals[:last_idx + 1]
solution = Solution()
print(solution.merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
print(solution.merge([[1,4],[4,5]]))
print(solution.merge([]))
print(solution.merge([[1, 4], [0, 1]]))
输出结果
[[1, 6], [8, 10], [15, 18]]
[[1, 5]]
[]
[[0, 4]]
网友评论