先对所有intervals按start值排序, 然后遍历, 如果当前Interval.start <= 已merged的大的Interval.end, 则扩展已merged的大的Interval.end。

# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    # @param intervals, a list of Interval
    # @return a list of Interval
    def merge(self, intervals):
        if intervals == []: return []
        intervals.sort(key = lambda x:x.start)
        res = []; prev = Start = End = None;
        for curr in intervals:
            if prev:
                if curr.start <= End:
                    End = max(End, curr.end)
                else:
                    res.append([Start, End])
                    Start = curr.start; End = curr.end
            else:
                Start = curr.start; End = curr.end
            prev = curr
        res.append([Start, End])
        return res