Traverse from the end to begin with O(1) space and O(n) time

  • -1

    class Solution(object):
    def merge(self, intervals):
    :type intervals: List[Interval]
    :rtype: List[Interval]
    # Sort by their begin time
    intervals.sort(key=lambda x:x.end)

        # From the end to the beginning.
        leng = len(intervals)-1
        while leng -1 >= 0:
            if intervals[leng-1].end >= intervals[leng].start:
                # Found overlap
                intervals[leng-1].start = min(intervals[leng-1].start, intervals[leng].start)
                intervals[leng-1].end = intervals[leng].end
                del intervals[leng]
            leng -= 1
        return intervals

Log in to reply

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