-
Notifications
You must be signed in to change notification settings - Fork 0
/
56MergeIntervals.py
59 lines (57 loc) · 1.88 KB
/
56MergeIntervals.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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
class comparatorA:
def __init__(self, interval):
self.interval = interval
def __lt__(self, other):
return self.interval[0] < other.interval[0]
newIntervals = [comparatorA(i) for i in intervals]
newIntervals.sort()
res = []
curr = 0
stayX = False
stayY = False
while curr + 1 < len(intervals):
# 3 conditions
if not stayX:
startx = newIntervals[curr].interval[0]
if not stayY:
currY = newIntervals[curr].interval[1]
nextX = newIntervals[curr + 1].interval[0]
nextY = newIntervals[curr + 1].interval[1]
if currY < nextX:
# result found
res.append([startx, currY])
curr += 1
stayX = False
stayY = False
elif currY < nextY:
curr += 1
stayX = True
stayY = False
else:
curr += 1
stayX = True
stayY = True
if not stayX:
startx = newIntervals[curr].interval[0]
if not stayY:
currY = newIntervals[curr].interval[1]
res.append([startx, currY])
return res
def merge2(self, intervals):
intervals.sort(key = lambda x : x[0])
res = []
res.append(intervals[0])
for i in range(1, len(intervals)):
if res[-1][1] < intervals[i][0]:
res.append(intervals[i])
elif res[-1][1] < intervals[i][1]:
res[-1][1] = intervals[i][1]
return res
sol = Solution()
sol.merge2([[1,4],[2,3]])