LintCode Q156 Merge Intervals in Python

  • Jinhai ZHOU
  • 4 Minutes
  • 2016年11月1日
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
"""
Definition of Interval.
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
# @param intervals, a list of Interval
# @return a list of Interval
def cmp_interval(self, x, y):
if x.start == y.start:
return cmp(x.end, y.end)
else:
return cmp(x.start, y.start)
def merge(self, intervals):
# write your code here
intervasl_sorted = sorted(intervals, cmp=self.cmp_interval)
ans = []
for interval in intervasl_sorted:
if len(ans) == 0:
ans.append(interval)
continue
if interval.start <= ans[len(ans)-1].end:
if interval.end > ans[len(ans)-1].end:
ans[len(ans)-1].end = interval.end
else:
ans.append(interval)
return ans
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。