个人主页Milestone-里程碑❄️个人专栏: 力扣hot100 CLinuxGitMySQL心向往之行必能至一、题目解读题目描述以数组intervals表示若干个区间的集合其中单个区间为intervals[i] [starti, endi]。请合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。示例分析示例 1输入[[1,3],[2,6],[8,10],[15,18]]输出[[1,6],[8,10],[15,18]]。解释区间[1,3]和[2,6]存在重叠合并为[1,6]其余区间无重叠直接保留。示例 2输入[[1,4],[4,5]]输出[[1,5]]。解释相邻区间也被视为重叠区间需要合并。示例 3输入[[4,7],[1,4]]输出[[1,7]]。解释输入区间无序需先排序再判断重叠。从示例中我们可以提炼出两个核心关键点输入区间可能无序、重叠 / 相邻区间都需要合并。二、解题思路贪心算法解决区间合并问题的核心逻辑是贪心策略核心思想是优先合并左端点小的区间通过维护当前合并区间的右端点逐步吸收后续重叠区间。具体步骤如下排序将所有区间按照左端点从小到大排序。排序后我们只需依次比较当前区间与已合并区间的重叠情况无需考虑乱序问题。遍历合并初始化一个结果数组用于存储最终的合并区间。遍历排序后的区间若结果数组为空直接将当前区间加入结果数组。若当前区间的左端点≤结果数组最后一个区间的右端点说明两个区间重叠 / 相邻需要合并 —— 更新结果数组最后一个区间的右端点为「两者右端点的最大值」。若当前区间的左端点结果数组最后一个区间的右端点说明无重叠直接将当前区间加入结果数组。三、代码实现C结合上述思路我们可以写出简洁高效的 C 代码代码中添加了详细注释便于理解cppclass Solution { public: vectorvectorint merge(vectorvectorint intervals) { // 第一步按区间左端点从小到大排序 sort(intervals.begin(), intervals.end()); vectorvectorint res; // 结果数组存储合并后的区间 for (auto interval : intervals) { // 情况1结果数组为空直接加入第一个区间 // 情况2当前区间左端点 结果数组最后一个区间的右端点无重叠直接加入 if (res.empty() || interval[0] res.back()[1]) { res.emplace_back(interval); } else { // 情况3有重叠合并区间更新右端点为最大值 res.back()[1] max(res.back()[1], interval[1]); } } return res; } };四、关键细节解析1. 为什么要按左端点排序排序是贪心算法的前提。排序后区间的左端点呈递增趋势我们只需关注当前区间与结果数组最后一个区间的右端点的关系就能线性遍历完成合并无需回溯将时间复杂度从暴力解法的 \(O(n^2)\) 降低到 \(O(n \log n)\)排序的时间复杂度。2. 为什么要用max更新右端点这是很多初学者容易忽略的点例如输入[[1,5],[2,3]]排序后第一个区间是[1,5]第二个区间是[2,3]。此时第二个区间完全被第一个区间包含若直接覆盖右端点会得到错误结果[1,3]而用max就能保留正确的右端点5。3. 关于emplace_back的使用代码中使用res.emplace_back(interval)而非res.push_back(interval)两者功能相同但emplace_back是直接在容器尾部构造对象避免了拷贝操作效率更高是 C11 及以上版本的推荐写法。五、复杂度分析时间复杂度\(O(n \log n)\)。其中 n 是区间的数量排序操作的时间复杂度为 \(O(n \log n)\)遍历操作的时间复杂度为 \(O(n)\)整体由排序主导。空间复杂度\(O(\log n)\)排序的系统栈空间或 \(O(n)\)存储结果的数组最坏情况无重叠需存储所有区间。六、总结合并区间问题是贪心算法在区间类问题中的典型应用其核心套路可以总结为排序定顺序遍历判重叠贪心合并区间。