问题背景

合并区间是一个经典的算法问题，通常在面试中被问到。给定一组区间，任务是将重叠的区间合并并返回不重叠的区间。

解决方法

为了解决合并区间问题，可以按照以下步骤进行：

  1. 首先，将给定的区间按照左边界进行排序。这是因为如果两个区间有交集，它们一定会有一个公共的左边界。
  2. 初始化一个结果列表，并将第一个区间放入结果列表。
  3. 遍历排序后的剩余区间，对于当前的区间：
    • 如果当前区间的左边界大于结果列表中最后一个区间的右边界，表示当前区间与结果列表中的区间没有交集，直接将当前区间加入结果列表。
    • 否则，表示当前区间与结果列表中的区间有交集，比较当前区间的右边界与结果列表中最后一个区间的右边界，将两个区间的右边界取较大值，更新结果列表中最后一个区间的右边界。
  4. 返回结果列表中的区间即可。

代码实现

class Solution:
    def merge(self, intervals):
        # 将区间按左边界排序
        intervals.sort(key=lambda x: x[0])
        # 初始化结果列表
        merged = []
        # 遍历区间
        for interval in intervals:
            # 如果结果列表为空或当前区间与结果列表最后一个区间无交集，直接将当前区间加入结果列表
            if not merged or interval[0] > merged[-1][1]:
                merged.append(interval)
            # 否则，更新结果列表最后一个区间的右边界
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

复杂度分析

时间复杂度：合并区间的时间复杂度为O(nlogn)，其中n是区间的个数。需要对区间进行排序，最坏情况下需要O(nlogn)的时间。

空间复杂度：合并后的区间的个数不会超过n，因此空间复杂度为O(n)。