python solution in place


  • 0
    R
    class Solution(object):
        def merge(self, intervals):
            intervals.sort(key=lambda x:(x.start,x.end))    #sort start first then end
            i=1
            while i<len(intervals):
                begin=i-1
                max_end=intervals[i-1].end
                while i<len(intervals) and  (intervals[i-1].end >= intervals[i].start or max_end>=intervals[i].start):
                    max_end=max(intervals[i-1].end,max_end)
                    max_end=max(intervals[i].end,max_end)
                    i+=1
                tmp = Interval(intervals[begin].start,max_end)
    
                if i-begin>1:    
                    for k in range(begin,i):
                        intervals.pop(begin)    #delete all merged section
                    intervals.insert(begin,tmp)    #insert new merge section
                    i=i-(i-begin)+1         #set i to new merge section next
                else:                   #no merge happened
                    i+=1
            return intervals
    

Log in to reply
 

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