LeetCode 第 56 题：合并区间 题目描述 给定一个区间的集合 intervals ，其中每个区间表示为 intervals[i] = [start_i, end_i] 。你需要合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需覆盖输入中的所有区间。 示例： 输入： intervals = [[1,3],[2,6],[8,10],[15,18]] 输出： [[1,6],[8,10],[15,18]] 解释：区间 [ 1,3] 和 [ 2,6] 重叠，合并为 [ 1,6 ]。 解题过程 问题分析 目标是将所有重叠的区间合并成更大的区间。 重叠的定义：如果区间 A 的结束点大于等于区间 B 的起始点，则 A 和 B 重叠（例如 [ 1,3] 和 [ 2,4 ]）。 关键点：需要高效检测重叠并合并，避免重复比较。 关键思路 如果区间按起始点排序，那么重叠的区间一定会相邻出现。例如，排序后只需比较当前区间和结果列表中最后一个区间即可判断是否合并。 步骤： 按每个区间的起始点升序排序。 遍历排序后的区间，逐个判断是否与已合并的最后一个区间重叠。 如果重叠，更新已合并区间的结束点（取最大值）；否则直接加入结果列表。 详细步骤 步骤 1：排序 对 intervals 按每个区间的第一个元素（start_ i）进行排序。例如： 输入 [[1,3],[2,6],[8,10],[15,18]] 排序后为 [[1,3],[2,6],[8,10],[15,18]] （本身已有序）。 步骤 2：初始化结果列表 创建空列表 merged ，用于存储合并后的区间。 步骤 3：遍历并合并 将第一个区间 [1,3] 加入 merged 。 遍历下一个区间 [2,6] ： 比较当前区间起始点（2）与 merged 最后一个区间的结束点（3）。 因为 2 ≤ 3，说明重叠，更新 merged 最后一个区间的结束点为 max(3, 6) = 6 。 此时 merged = [[1,6]] 。 遍历 [8,10] ：起始点 8 > 6，不重叠，直接加入 merged = [[1,6],[8,10]] 。 遍历 [15,18] ：起始点 15 > 10，不重叠，加入 merged = [[1,6],[8,10],[15,18]] 。 步骤 4：返回结果 最终 merged 即为答案。 复杂度分析 时间复杂度：O(n log n)，主要来自排序（n 为区间数量）。 空间复杂度：O(n)，存储合并结果（若考虑排序的栈空间，最坏为 O(log n)）。 边界情况处理 空输入：直接返回空列表。 无重叠区间：如 [[1,2],[3,4]] ，所有区间均直接加入结果。 完全覆盖：如 [[1,4],[2,3]] ，合并为 [1,4] （取结束点最大值）。 通过排序和一次遍历，即可高效合并所有重叠区间，确保结果正确且无冗余。