题解 | 合并区间

最简单的先排序再合并的时间复杂度是O(nlogn)，如下

class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        if len(intervals) == 0: return []
        so_int = sorted(intervals, key=lambda x: x.start)
        result = []
        working = so_int[0]
        for inter in so_int:
            if inter.start <= working.end:
                working.end = max(inter.end, working.end)
            else:
                result.append(working)
                working = inter

        result.append(working)

        return result

我们关注一下核心的解法2，如何达到O(val)常数复杂度。注意到我们可以把合并区间看成是 从起点 i 开始，能找到的最远的终点是多远。那么这是一个在数轴上画线的问题，可以直接转换成基于桶排序的思想，利用数组下标天然的“数轴”属性。

class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        if len(intervals) == 0: return []
        val = 200001 # 2 * 10^5 + 1
        bukkit = [-1] * val
        for i in intervals:
            bukkit[i.start] = max(bukkit[i.start], i.end) # 记录从i.start开始的最远的距离, O(n)

        # 关键的 O(val) 实现
        res = []
        start, end = -1, -1
        for i in range(val):
            if bukkit[i] != -1: # 发现一个新区间
                if i <= end: # 如果这个区间和当前区间有重叠
                    end = max(end, bukkit[i]) # 合并，注意保留比较远的结尾
                else: # 这是一个新的区间
                    if start != -1: # 这不是第一个区间的话
                        res.append(Interval(start, end)) # 保存当前结果
                    start, end = i, bukkit[i] # 开始处理新的区间
        
        if start != -1 and end != -1:
            res.append(Interval(start, end)) # 把最后一个区间存上
        
        return res