LC 56 Merge intervals

Given a collection of intervals, merge all overlapping intervals.

Ideas

We first need to sort the given intervals based on the starting position.
Then there will be 3 scenarios:

  1. Contain
  2. Intersect
  3. Non-intersect

We use an aux array called res ** to hold all the intervals that have been processed. Every intervals in **res except the last one, is finished and is in the right order.

We first start with res = [intervals[0]] and then iterate from intervals[1] to intervals[-1].
For interval[i]:

  1. if res[-1] contains interval[i], do nothing
  2. If res[-1] intersect interval[i], update res[i]’s end
  3. If non intersect, append interval[i] to res.
    def merge(self, intervals: 'List[Interval]') -> 'List[Interval]':
        #first sort based on the first index
        intervals = sorted(intervals, key=lambda x: x.start)

        if not intervals:return []
        res = [intervals[0]]
        for i in range(1, len(intervals)):
            cur_left = res[-1].start
            cur_right = res[-1].end
            if cur_right >= intervals[i].end: #contain
                pass
            elif intervals[i].start <= cur_right <= intervals[i].end:
                res[-1].end = intervals[i].end
            else:
                res.append(intervals[i])

        return res

Bugs

Have to sort!!

Intersection occurs when intervals[i].start == res[-1].end as well

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax