合并区间

题目

给出一个区间的集合，请合并所有重叠的区间。

思路

首先按照起始点进行排序，然后一一合并。
(什么时候需要合并，什么时候不需要合并，画两条线段比划一下就知道条件了）

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        merged = []
        for interval in intervals:
            # 如果列表为空，或者当前区间与上一区间不重合，直接添加
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # 否则的话，我们就可以与上一区间进行合并
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged