Accepted Python solution O(nlogn) using sorting function


  • 0
    X
    class Solution:
        # @param intervals, a list of Interval
        # @return a list of Interval
        def merge(self, intervals):
            if intervals == []:
                return []
            intervals.sort(key=lambda interval: interval.start)
            result = [intervals[0]]
            for i in range(1,len(intervals)):
                prevRange = result.pop()
                start,end = prevRange.start, prevRange.end
                updated = False
                if intervals[i].start <= end:
                    start = min(intervals[i].start, start)
                    updated = True
                    end = max(intervals[i].end, end)
                result.append(Interval(start, end))
                if not updated:
                    result.append(intervals[i])
            return result
    

    Sort the intervals first, so that we can iterate through the sorted list in linear time later.


  • 0
    G

    Same idea but simpler dealing with new start and end.

    class Solution:
        # @param intervals, a list of Interval
        # @return a list of Interval
        def merge(self, intervals):
            if intervals == []:
                return []
            intervals.sort(key=lambda interval: interval.start)
        	ans = [intervals[0]]
        	for inter in intervals[1:]:
        		last = ans[-1]
        		if inter.start <= last.end:
        			last.end = max(inter.end, last.end)
        		else:
        			ans.append(inter)
            return ans
    

Log in to reply
 

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