题目
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
例如
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
代码
intervals按照区间左端点升序排列是为了进行重叠判断和合并操作的时候只用操作当前元素和栈顶元素。
其实，对于已经按照上面规则排序好的区间
[
a
1
,
b
1
]
,
[
a
2
,
b
2
]
,
.
.
.
.
,
[
a
n
,
b
n
]
[a1,b1],[a2,b2],….,[an,bn]
[
a
1
,
b
1
]
,
[
a
2
,
b
2
]
,
….
,
[
an
,
bn
]
如果
[
a
1
,
b
1
]
[a1,b1]
[
a
1
,
b
1
]
和
[
a
2
,
b
2
]
[a2,b2]
[
a
2
,
b
2
]
都不重叠，说明
b
1
<
a
2
<
a
3
<
.
.
.
b1<a2<a3<…
b
1
<
a
2
<
a
3
<
…
即
[
a
1
,
b
1
]
[a1,b1]
[
a
1
,
b
1
]
与之后的区间更不可能重叠了。故排序后，我们只需要做当前区间和栈顶区间的重叠判断即可。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# 只有一个区间
if len(intervals)==1:
return intervals
# 合并重叠区间S1,S1
def f(S1,S2):
left=min(S1[0],S2[0])
right=max(S1[1],S2[1])
return [left,right]
# 判断区间S1,S2是否重叠 False不重叠
def g(S1,S2):
if S1[1]<S2[0] or S2[1]<S1[0]:
return False
else:
return True
# 按照区间左端点升序排列
intervals=sorted(intervals,key=lambda x:x[0])
stack=[intervals[0]] # 记录合并后的区间
# 每当遍历一个新区间时，和栈顶区间做重叠判断，若重叠合并后再入栈
for i in range(1,len(intervals)):
if g(stack[-1],intervals[i]):
tmp=f(stack.pop(),intervals[i])
stack.append(tmp)
else:
stack.append(intervals[i])
return stack