LC 56合并区间Merge Intervals　中等

合并所有相互重叠的区间，返回不重叠的区间列表。

思路 按左端点排序后顺序扫描：当前区间与答案末尾有交则更新其右端点，否则加入新区间。时间 O(n log n)。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        ans = []
        for a, b in intervals:
            if ans and a <= ans[-1][1]:
                ans[-1][1] = max(ans[-1][1], b)
            else:
                ans.append([a, b])
        return ans