from functools import cmp_to_key
# class Interval:
#     def __init__(self, a=0, b=0):
#         self.start = a
#         self.end = b

class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        if len(intervals) == 0:
            return intervals

		# 排序
        intervals.sort(key=cmp_to_key(lambda a,b:a.start-b.start))
        res = []
        res.append(intervals[0])

        for i in range(len(intervals)):
            if intervals[i].start <= res[-1].end: # 说明有重叠
                res[-1].end = max(res[-1].end, intervals[i].end) # 合并区间
            else:
                res.append(intervals[i])

        return res

解题思路

• 先判断特殊情况；
• 排序；
• 循环遍历，判断是否有重叠，如果有重叠，则更新res最后一个元素的end值；否则，直接加入到res中。

复杂度

• 时间复杂度为O(nlogn)；
• 空间复杂度为O(1)。