（14）LeetCode 56. 合并区间

LeetCode 56. 合并区间

📝 题目描述

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠，合并为 [1,6]。

示例 2：

输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 被视为重叠区间（闭区间）。

---

💡 解题思路

核心思想

1. 排序：按照每个区间的左端点升序排序，这样所有区间按起始位置有序排列。
2. 一次遍历合并：
   • 用两个变量l和r记录当前合并区间的左右端点。
   • 依次检查后续区间：
     • 若当前区间的左端点> r，说明与当前合并区间没有重叠，将当前合并区间存入结果，并更新l和r为新区间的端点。
     • 否则，说明有重叠，更新r = max(r, current_end)，合并区间。
3. 收尾：遍历结束后，将最后一个合并区间加入结果。

为什么排序是关键？

排序后，我们只需从左到右扫描一次，因为左端点递增，任何重叠只可能发生在相邻区间之间，无需回头检查。

重叠判断条件

• 区间[a, b]和[c, d]（已排序，a ≤ c）重叠当且仅当c ≤ b（闭区间，等于也算重叠）。
• 在代码中，我们判断intervals[i][0] > r则为不重叠，否则为重叠。

---

🧑‍💻 C++ 代码实现

classSolution{public:vector<vector<int>>merge(vector<vector<int>>&intervals){vector<vector<int>>res;// 存储合并后的结果if(intervals.empty())returnres;// 处理空输入// 1. 按区间左端点排序sort(intervals.begin(),intervals.end());// 2. 初始化当前合并区间intl=intervals[0][0],r=intervals[0][1];// 3. 遍历后续区间for(inti=1;i<intervals.size();++i){if(intervals[i][0]>r){// 无重叠res.push_back({l,r});// 保存当前合并区间l=intervals[i][0];// 开始新区间r=intervals[i][1];}else{// 有重叠r=max(r,intervals[i][1]);// 合并，更新右端点}}// 4. 加入最后一个区间res.push_back({l,r});returnres;}};

---

🔍 代码细节解析

步骤	说明
sort(intervals.begin(), intervals.end())	按左端点升序排序，左端点相同则按右端点升序（不影响合并逻辑）
if (intervals[i][0] > r)	判断无重叠的条件：当前左端点严格大于当前右端点（闭区间，等于则重叠）
res.push_back({l, r})	将合并好的区间存入结果，注意用{}初始化vector<int>
r = max(r, intervals[i][1])	有重叠时，取两个右端点的较大值，扩大合并区间
最后res.push_back({l, r})	循环结束后，最后一个合并区间尚未加入，需补加

---

⏱ 复杂度分析

• 时间复杂度：O(n log n)，其中 n 是区间个数。主要耗费在排序上，遍历部分为 O(n)。
• 空间复杂度：O(n)（用于存储结果）。若不计结果数组，排序的栈空间为 O(log n)（快速排序）。

---

🧪 示例模拟

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]

步骤	当前区间	当前合并区间[l, r]	操作
初始化	-	[1, 3]	从第一个区间开始
i=1	[2,6]	[1, 3]→[1, 6]	重叠，扩展r=6
i=2	[8,10]	[1, 6]	无重叠，保存[1,6]，新合并区间[8,10]
i=3	[15,18]	[8,10]	无重叠，保存[8,10]，新合并区间[15,18]
结束	-	[15,18]	保存最后一个区间

最终结果：[[1,6],[8,10],[15,18]]

---

⚠️ 注意事项

• 输入区间是闭区间，因此[1,2]和[2,3]视为重叠，合并为[1,3]。
• 排序是必须的，否则无法通过一次遍历判断所有重叠。
• 处理空输入时，直接返回空数组，避免访问越界。

---