一、 题目来源与描述题目来源LeetCode 第 56 题 - 合并区间 (Merge Intervals)难度中等题目描述以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi]。请你合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。二、 输入数据结构深度解析在解答本题前我们需要明确输入数据的结构。题目给出的输入 intervals 其实是一个二维数组在 C 中为二维向量vectorvectorint。外层维度表示有多少个区间。例如 intervals.size() 代表区间的总个数。内层维度固定长度为 2。intervals[i][0] 代表第 i 个区间的左端点起始位置intervals[i][1] 代表第 i 个区间的右端点结束位置。示例解析输入intervals [[1,3],[2,6],[8,10],[15,18]]这代表集合中有 4 个区间区间 1从 1 到 3区间 2从 2 到 6区间 3从 8 到 10区间 4从 15 到 18三、 核心算法思路排序 贪心这道题如果直接两两比较时间复杂度会非常高。最优的解法基于一个关键的预处理步骤排序。1.为什么需要排序如果区间是无序的比如 [[8,10], [1,3], [2,6]]我们很难判断 [1,3] 和 [2,6] 是否重叠因为它们不相邻。但如果我们按区间的左端点进行升序排序数组就会变成 [[1,3], [2,6], [8,10]]。此时我们只需要从左到右遍历一次比较当前区间与前一个已合并区间的关系即可。2.贪心策略与合并逻辑排序后我们维护一个结果数组 merged。遍历排序后的区间对于每一个当前区间 curr与 merged 中的最后一个区间 last 进行比较情况 A发生重叠或相接如果 curr 的左端点≤last 的右端点即 curr[0] last[1]说明两个区间有交集。操作更新 last 的右端点取两者右端点的最大值last[1] max(last[1], curr[1])。(注意这里不需要更新左端点因为我们已经按左端点排序last的左端点一定小于等于curr的左端点)情况 B没有重叠如果 curr 的左端点last 的右端点即 curr[0] last[1]说明两个区间完全分离。操作直接将 curr 加入 merged 数组成为新的 last。3.算法流程图解以 intervals [[1,3],[2,6],[8,10],[15,18]] 为例排序已经是升序。初始化merged [[1,3]]遍历[2,6]2 3 (重叠) - 更新 merged 末尾为 [1, max(3,6)] [1,6]。此时 merged [[1,6]]遍历[8,10]8 6 (不重叠) - 直接加入。此时 merged [[1,6], [8,10]]遍历[15,18]15 10 (不重叠) - 直接加入。此时 merged [[1,6], [8,10], [15,18]]结束返回 merged。四、 C 代码实现class Solution { public: vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vectorvectorint merged; merged.push_back(intervals[0]); for (int i 1; i intervals.size(); i) { int last_right merged.back()[1]; int curr_left intervals[i][0]; int curr_right intervals[i][1]; if (curr_left last_right) { merged.back()[1] max(last_right, curr_right); } else { merged.push_back(intervals[i]); } } return merged; } };五、 复杂度分析时间复杂度O(NlogN)主要消耗在排序上C 的 std::sort 平均时间复杂度为O(NlogN)。遍历合并的过程只需要一次线性扫描时间复杂度为O(N)。总体时间复杂度为O(NlogN)其中N是区间的数量。空间复杂度O(logN)或O(N)如果不考虑返回结果所占用的空间主要取决于排序算法的递归栈空间通常为O(logN)。如果考虑返回结果 merged 数组最坏情况下所有区间都不重叠需要存储N个区间空间复杂度为O(N)。