Python solution with one loop


  • 0
    Z
    class Solution(object):
        def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            if not newInterval:
                return intervals
            if not intervals:
                intervals.append(newInterval)
                return intervals
            #mix all start points and end points
            starts = list(map(lambda a:a.start,intervals))
            ends = list(map(lambda a:a.end, intervals))
            starts.append(newInterval.start)
            ends.append(newInterval.end)
            starts.sort()
            ends.sort()
            rs = []
            hold = False
            for i in range(len(starts)-1):
                start = starts[i]
                if ends[i]<starts[i+1]:#no overlap
                    if hold:
                        rs.append(Interval(holdStart,ends[i]))
                        hold = False
                    else:
                        rs.append(Interval(start,ends[i]))
                elif i == len(starts)-2:#overlap with the last interval
                        if hold:
                            rs.append(Interval(holdStart,ends[i+1]))
                            hold = False
                        else:
                            rs.append(Interval(start,ends[i+1]))
                elif not hold:#overlap with next interval, and we are not holding a start point
                    hold = True
                    holdStart = start
            #if the last interval is a new intact interval, then add it
            if ends[-2]<starts[-1]:
                rs.append(Interval(starts[-1],ends[-1]))
            return rs
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.