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