56. 合并区间

56. 合并区间

方法 1：排序

思路

按照每个间隔的左端点排序。排序之后，根据当前间隔的左端点的位置（设为 x）与 ans 中最右侧间隔的右端点的位置（设为 y）判断这两个间隔是否进行合并。如果 y <= x，则说明 ans 中最右侧间隔的右端点在当前间隔的左端点的左侧，这两个区间可以进行合并，否则直接将当前端点加入 ans 即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda p: p[0])
        ans = []
        for p in intervals:
            if ans and p[0] <= ans[-1][1]:
                ans[-1][1] = max(p[1], ans[-1][1])
            else:
                ans.append(p)
        return ans

复杂度

时间复杂度：$O(n \log n)$。排序花费时间。
空间复杂度：$O(1)$。排序的栈开销和返回值不计入。