Python solution with detailed explanation


  • 0
    G

    Solution

    Merge Intervals https://leetcode.com/problems/merge-intervals/

    Algorithm

    • Sort the list by start times.
    • Create a result list and insert the first interval in it. Now iterate the remaining intervals in sequence and try merging using the rules in this diagram: https://goo.gl/photos/ZyeAHc5GHzhKM9Ru8
    class Solution(object):
        def merge(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: List[Interval]
            """
            if intervals == []:
                return []
            intervals.sort(key = lambda x: x.start)
            result = [intervals[0]]
            for i in range(1, len(intervals)):
                i1, i2 = result[-1], intervals[i]
                if i2.start > i1.end:
                    result.append(i2)
                elif i2.end >= i1.end:
                    i1.end = i2.end
            return result    
    

Log in to reply
 

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