56. Merge Intervals

题目

解题思路

假设intervals = [[s1, e1], [s2, e2]]
此题解题思路比较简明，首先是排序。如果interval中的起始点都按顺序排列的话，我们可以保证下一段interval一定会以下两种结果之一：

1. 覆盖得到新的result [-1] (即s2<=e1)
2. 独立于之前的result [-1]被append进入result (即s2>e1)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []       
        intervals.sort(key = lambda x: x[0])
        result.append(intervals[0])
        for lst in intervals:         
            if lst[0] <= result[-1][1]:
                # overlap
                if lst[1] > result[-1][1]:
                    result[-1][1] = lst[1]
            else :
                result.append(lst)
        return result

注意

因为array专区，我们不考察sorting algorithm。此处sort的时间复杂度为O(nlgn)，我们可以简单看做用了merge sort/ quick sort等方法完成的排序。O(nlgn + n) 为程序的时间复杂度。