1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
# 56. Merge Intervals
"""
given an array of 'intervals' where 'intervals[i] = [start_i, end_i]', merge
all overlapping intervals, and return an array of the non-overlapping
intervals that cover all the intervals in the input.
"""
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
stack = []
for i in sorted(intervals, key=lambda i: i[0]):
if stack and i[0] <= stack[-1][1]:
stack[-1][1] = max(stack[-1][1], i[1])
else:
stack += [i]
return stack
if __name__ == "__main__":
obj = Solution()
print(obj.merge(intervals=[[1, 3], [2, 6], [8, 10], [15, 18]]))
print(obj.merge(intervals=[[1, 4], [4, 5]]))
|