56. Merge Intervals Leetcode

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
この問題の作り方はいろいろありますが、stackを使ったものもあれば直接計算したものもあります.ここでは直接計算の方法を採用します.
1.intervalsをstartでソートする
2.startを比較するpreがあれば.start<=post.start<=pre.それは...end=max(pre.end,post.end)NOの場合はmergeを行わない
並べ替えを行うので時間的複雑度はO(nlogn+n)=O(nlogn)
We need to sort the intervals based on start, then we compare pre.start with post.start and pre.end. If post.start fall in [pre.start, pre.end] we need to merge the two based on 
max(pre.end,post.end)
otherwise, we add the interval to the solution directly.
The time complexity in this problem is O(nlogn)

# Definition for an interval.
# 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):
        solution=[]
        intervals.sort(key=lambda x:x.start)
        for index in range(len(intervals)):
            if solution==[]:
                solution.append(intervals[index])
            else:
                size=len(solution)
                if solution[size-1].start<=intervals[index].start<=solution[size-1].end:
                    solution[size-1].end=max(solution[size-1].end,intervals[index].end)
                else:
                    solution.append(intervals[index])
        return solution