题目要求：
- 寻找插入位置，也是最简单的情况：根据newIntervals.start和intervals[i].end比较，如果新插入的开始大于一个元素的末尾，那么插入位置肯定不是这个元素。
- 确定最后的位置：如果newIntervals.end < intervals[i].start就要不停的遍历，所以相反的条件就是while条件newIntervals.end >= intervals[i].start，就可以执行while语句。-
# Time: O(n)
# Space: O(1)
class Interval(object):
def __init__(self, s=0, t=0):
self.start = s
self.end = t
def __repr__(self):
return "[{}, {}]".format(self.start, self.end)
class Solution(object):
def insert(self, intervals, newInterval):
"""
:param intervals: List[Interval]
:param nreinterval: Interval
:return: List[Interval]
"""
result = []
i = 0
while i < len(intervals) and newInterval.start > intervals[i].end: #找到需要插入更新的位置
result.append(intervals[i])
i += 1
while i < len(intervals) and newInterval.end >= intervals[i].start: #从上面的位置开始
newInterval = Interval(min(newInterval.start, intervals[i].start), \
max(newInterval.end, intervals[i].end))
i += 1
result.append(newInterval)
for interval in range(i, len(intervals)):
result.append(intervals[interval])
return result
if __name__ == "__main__":
print(Solution().insert([Interval(1, 2), Interval(3, 5), Interval(6, 7), Interval(8, 10), Interval(12, 16)], Interval(4, 9)))
