合并区间

https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1046/

image.png

先排序吧，好操作一点。
排序好了后，后面一个的start只要大于等于前面一个的end，说明就要合并，否则就单独一个。

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        if not intervals or len(intervals) ==1:
            return intervals
        
        intervals.sort(key=lambda x:x[0])
        result = [intervals[0]]
        for i in range(1,len(intervals)):
            if intervals[i][0]<=result[-1][1]:
                result[-1][1] = max(result[-1][1],intervals[i][1])
            else:
                result.append(intervals[i])
        return result

如果不排序，只能每个区间去找和他start相邻的两个区间，然后看这三个区间能否合并，查找也要时间复杂度的，不会比排序后快多少。