57. &56 Insert Interval

题目要求：

• 题目要求
• 寻找插入位置，也是最简单的情况：根据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)))