[SwapLine]57. Insert Interval

• 分类：SwapLine
• 时间复杂度: O(n)

57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

代码：

方法:

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        
        if intervals==None or len(intervals)==0:
            return [newInterval]
        
        res=[]
        i=0
        while i<len(intervals):
            if i==len(intervals):
                if newInterval.start>=intervals[i-1].start:
                    intervals.insert(i,newInterval)
                else:
                    intervals.insert(i-1,newInterval)
                break
            if newInterval.start<=intervals[i].start:
                intervals.insert(i,newInterval)
                break
            i+=1
        
        i=0
        last=intervals[i]
        print(last.start,last.end)
        while(i<len(intervals)):
            if intervals[i].start<=last.end:
                last.end=max(intervals[i].end,last.end)
            else:
                res.append(last)
                last=intervals[i]
            i+=1
        res.append(last)
               
        return res

讨论：

1.这种日常觉得自己傻叉是怎么回事？