Simple O(n) python solution with explanation


  • 0
    C
    • Sort the list based on start times of the intervals

    • Iterate with two pointers previous and current

    • If the current has a start time greater than the end time of the previous, thus there's no overlap, add pervious to a result list.

    • Else mutate previous and continue.

    • Upon exit add previous

        def merge(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: List[Interval]
            """
            if not intervals or len(intervals) == 0:
                return []
            results = []
            sorted_intervals = sorted(intervals, key=lambda x: x.start)
            previous = sorted_intervals[0]
            for i in range(1, len(sorted_intervals)):
                current = sorted_intervals[i]
                if previous.end < current.start:
                    results.append(current)
                    previous = current
                elif previous.end >= current.start:
                    if previous.end <= current.end:
                        new_interval = Interval(previous.start, current.end)
                    else:
                        new_interval = Interval(previous.start, previous.end)
                    previous = new_interval
            results.append(previous)
            return results
      

Log in to reply
 

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