Straightforward python solution. Runtime O(NlogN)


  • 0

    This problem is easier than I thought (because it is labeled hard). Simply have two pointers. One pointing to the most recent merged interval, another pointing to the interval to come. Sorting the given collection of intervals takes O(NlogN), where N is the number of intervals we have.

    class Solution(object):
        def merge(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: List[Interval]
            """
            if len(intervals) <= 1:
                return intervals
            
            intervals = sorted(intervals, key=lambda x: x.start)
            result = [intervals[0]]
            i = 0
            j = 1
            while j < len(intervals):
                if result[i].start <= intervals[j].start and intervals[j].start <= result[i].end:
                    result[i] = Interval(result[i].start, max(result[i].end, intervals[j].end))
                else:
                    result.append(intervals[j])
                    i += 1
                j += 1
            return result
    

Log in to reply
 

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