Concise O(nlogn) Python Solution

  • 0

    Sorts the list by interval start, then merges them sequentially

    class Solution(object):
        def merge(self, intervals):
            :type intervals: List[Interval]
            :rtype: List[Interval]
            Solution: Sort intervals by start. Merge intervals by going down the list
            Runtime: O(nlogn)
            if len(intervals) == 0:
                return intervals
            if len(intervals) == 1:
                return intervals
            sorted_intervals = sorted(intervals, key=lambda x: (x.start, x.end))
            merged_intervals = [sorted_intervals[0]]
            for idx, interval in enumerate(sorted_intervals):
                if interval.start <= merged_intervals[-1].end:
                    merged_intervals[-1].end = max(interval.end, merged_intervals[-1].end)
            return merged_intervals

Log in to reply

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