（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;}};

🔍 代码细节解析

⏱ 复杂度分析

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

🧪 示例模拟

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

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

⚠️ 注意事项

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