LintCode Q30 Insert Interval in Python

  • Jinhai ZHOU
  • 5 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
33
34
35
36
37
38
39
"""
Definition of Interval.
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
"""
Insert a new interval into a sorted non-overlapping interval list.
@param intevals: Sorted non-overlapping interval list
@param newInterval: The new interval.
@return: A new sorted non-overlapping interval list with the new interval.
"""
def insert(self, intervals, newInterval):
result = []
if newInterval is None:
return intervals
# write your code here
inserted = False
for interval in intervals:
if not inserted and newInterval.start < interval.start:
result.append(newInterval)
inserted = True
if not inserted and newInterval.start >= interval.start and newInterval.start <= interval.end:
interval.end = max(newInterval.end, interval.end)
result.append(interval)
inserted = True
if len(result) == 0:
result.append(interval)
elif result[-1].end < interval.start:
result.append(interval)
else: # result > 0 and result[-1] >= interval.start
result[-1].end = max(result[-1].end, interval.end)
if not inserted:
result.append(newInterval)
return result
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。