-
Notifications
You must be signed in to change notification settings - Fork 1
/
0056.py
39 lines (31 loc) · 1.09 KB
/
0056.py
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
29
30
31
32
33
34
35
36
37
38
39
class Solution:
def within(self, left, right, pos):
return left <= pos and pos <= right
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
longest = defaultdict(int)
for i in intervals:
left = i[0]
right = i[1]
longest[left] = max(longest[left], right)
again = True
while again:
start = sorted(longest.keys())
again = False
for a in range(len(start)):
for b in range(a+1, len(longest)):
left = start[a]
right = longest[left]
next = start[b]
if not self.within(left, right, next):
break
if longest[next] > right:
longest[left] = longest[next]
del longest[next]
b -= 1
again = True
if again:
break
result = []
for i in longest:
result.append([ i, longest[i] ])
return result