（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]。
  • 排序是必须的，否则无法通过一次遍历判断所有重叠。
  • 处理空输入时，直接返回空数组，避免访问越界。