普通数组---合并区间-平芜编程栈

🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

<<Git>><<MySQL>>

🌟心向往之行必能至

一、题目解读

题目描述

以数组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++ 代码，代码中添加了详细注释，便于理解：

cpp

class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { // 第一步：按区间左端点从小到大排序 sort(intervals.begin(), intervals.end()); vector<vector<int>> 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是直接在容器尾部构造对象，避免了拷贝操作，效率更高，是 C++11 及以上版本的推荐写法。

五、复杂度分析

时间复杂度：\(O(n \log n)\)。其中 n 是区间的数量，排序操作的时间复杂度为 \(O(n \log n)\)，遍历操作的时间复杂度为 \(O(n)\)，整体由排序主导。
空间复杂度：\(O(\log n)\)（排序的系统栈空间）或 \(O(n)\)（存储结果的数组，最坏情况无重叠，需存储所有区间）。