合并区间算法 题目描述：给定一个区间集合，合并所有重叠的区间。例如，输入区间集合为 [ [ 1,3], [ 2,6], [ 8,10], [ 15,18]]，合并后的结果应为 [ [ 1,6], [ 8,10], [ 15,18]]。因为区间 [ 1,3] 和 [ 2,6] 存在重叠，可以合并为 [ 1,6 ]。 解题过程： 问题理解与关键观察 核心任务是识别并合并那些在数轴上相互重叠或相邻的区间。 一个关键观察是：如果我们将所有区间按照每个区间的 起始点（左端点） 进行排序，那么需要合并的区间在排序后的列表中将会是连续的。这使得我们可以通过一次线性扫描来完成合并。 算法步骤 这是一个经典的贪心算法问题，步骤如下： 步骤一：边界情况处理 首先检查输入的区间列表。如果列表为空或只包含一个区间，那么它本身就已经是合并后的结果，直接返回即可。 步骤二：按区间起点排序 使用排序算法（例如快速排序）对所有区间进行排序，排序的依据是每个区间的第一个元素（即区间的起始点）。 步骤三：初始化合并列表 创建一个新的空列表（或数组） merged 用于存放合并后的结果。 将排序后的第一个区间添加到 merged 列表中。这个区间将作为我们当前正在考察和尝试合并的“基准区间”。 步骤四：遍历与合并 从第二个区间开始，依次遍历排序后的每一个区间（我们称当前正在遍历的区间为“当前区间”）： 情况一：存在重叠，进行合并 比较 merged 列表中 最后一个区间 的结束点（右端点）与“当前区间”的起始点。 如果 当前区间的起始点 <= merged最后一个区间的结束点 ，这说明两个区间存在重叠（或刚好相邻）。 此时，我们不需要将当前区间作为一个新区间加入 merged 列表，而是 扩展 merged 列表中最后一个区间的结束点。 新的结束点取 max(merged最后一个区间的结束点， 当前区间的结束点) 。这是因为当前区间可能完全包含在基准区间内，也可能延伸出去。 情况二：无重叠，直接添加 如果 当前区间的起始点 > merged最后一个区间的结束点 ，这说明两个区间完全分离，没有重叠。 此时，直接将“当前区间”作为一个新的独立区间添加到 merged 列表的末尾。这个新区间将成为新的“基准区间”，用于后续的比较。 示例演示 让我们用题目中的例子 [[1,3], [2,6], [8,10], [15,18]] 来走一遍流程。 步骤一 ：列表包含多个区间，继续。 步骤二 ：按起始点排序。原列表已经基本有序，排序后为 [[1,3], [2,6], [8,10], [15,18]] 。 步骤三 ：初始化 merged = [] 。将第一个区间 [1,3] 加入， merged = [[1,3]] 。 步骤四：遍历与合并 处理 [2,6] ： 当前 merged 最后一个区间是 [1,3] ，其结束点是 3 。 当前区间 [2,6] 的起始点是 2 。 判断： 2 <= 3 ？ 是 ，存在重叠。 进行合并： [1,3] 的结束点更新为 max(3, 6) = 6 。 现在 merged = [[1,6]] 。 处理 [8,10] ： 当前 merged 最后一个区间是 [1,6] ，其结束点是 6 。 当前区间 [8,10] 的起始点是 8 。 判断： 8 <= 6 ？ 否 ，无重叠。 直接添加：将 [8,10] 加入 merged 。 现在 merged = [[1,6], [8,10]] 。 处理 [15,18] ： 当前 merged 最后一个区间是 [8,10] ，其结束点是 10 。 当前区间 [15,18] 的起始点是 15 。 判断： 15 <= 10 ？ 否 ，无重叠。 直接添加：将 [15,18] 加入 merged 。 最终 merged = [[1,6], [8,10], [15,18]] 。 复杂度分析 时间复杂度 ：O(n log n)，其中主要的开销来自于最初的排序步骤。之后的线性扫描是 O(n)。 空间复杂度 ：O(log n) 或 O(n)，这取决于排序算法的实现。除了存储结果的空间外，排序本身可能需要 O(log n) 的栈空间（如快速排序）或 O(n) 的额外空间（如归并排序）。输出列表 merged 在最坏情况下（无任何重叠）需要 O(n) 空间。