LeetCode - 56. 合并区间

目录

题目

过程分析

读者可能出现的错误写法

正确写法

---

题目

56. 合并区间 - 力扣（LeetCode）

过程分析

以示例1为例，说明双指针法的合并过程：

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

• 首先对区间按起始位置排序（已经是排好序的）

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

• 初始化双指针

left = 1 (第一个区间的左边界)

right = 3 (第一个区间的右边界)

result = [] (结果数组，初始为空)

开始遍历：

• i=1, 检查区间[2,6]

• 2 <= right(3)，有重叠

• 更新 right = max(3, 6) = 6

• 当前状态: left=1, right=6, result=[]

• i=2, 检查区间[8,10]

• 8 > right(6)，无重叠

• 将当前合并区间加入结果: result.push_back([1,6])

• 开始新的合并区间: left=8, right=10

• 当前状态: left=8, right=10, result=[[1,6]]

• i=3, 检查区间[15,18]

• 15 > right(10)，无重叠

• 将当前合并区间加入结果: result.push_back([8,10])

• 开始新的合并区间: left=15, right=18

• 当前状态: left=15, right=18, result=[[1,6], [8,10]]

循环结束，将最后的合并区间加入结果

result.push_back([15,18])

最终结果: result = [[1,6], [8,10], [15,18]]

返回: [[1,6], [8,10], [15,18]]

读者可能出现的错误写法

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {//先进行初始化判断if(intervals.empty()){return 0;}//进行排序sort(intervals.begin(),intervals.end());//初始化双指针int left = intervals[0][0];int right = intervals[0][1];//初始化结果集vector<vector<int>> result;//进行循环比较是否出现重叠for(int i =1;i<intervals.size();i++){if(right > intervals[i][0])  //说明有重叠的部分{right = intervals[i][0];result.push_back(left,right);}left = intervals[i][0];right = intervals[i][1];result.push_back(left,right);}return result;}
};

返回值错误:

if(intervals.empty())
{return 0;  // 错误
}

• 错误：函数返回类型是 vector<vector<int>>，但你返回了整数 0

• 正确：应该返回空向量 return {};

重叠判断逻辑错误：

   if(right > intervals[i][0])  //说明有重叠的部分{right = intervals[i][0];  // 错误result.push_back(left,right);  // 错误}

• 错误一：当有重叠时，右边界应该取两个区间右边界的最大值，而不是将右边界设为当前区间的左边界

• 错误二：这里的重叠条件正确（right > intervals[i][0]表示有重叠），但更常见的写法是 intervals[i][0] <= right，语义上更清晰

• 正确：right = max(right, intervals[i][1]);

push_back 用法错误：

   result.push_back(left,right);  // 错误

• 错误：push_back 只接受一个参数，不能传两个单独的整数

• 正确：result.push_back({left, right}); 传入一个包含两个元素的向量

逻辑结构问题:

   if(right > intervals[i][0])  //说明有重叠的部分{right = intervals[i][0];result.push_back(left,right);}left = intervals[i][0];  // 这行代码无条件执行right = intervals[i][1];  // 这行代码无条件执行result.push_back(left,right);  // 这行代码无条件执行

• 错误：无论是否有重叠，都会重置 left 和 right，并且每次循环都会无条件添加一个新区间

• 正确：只有在没有重叠时，才应该添加当前合并区间并重置 left 和 right

缺少最后一个区间处理:

• 错误：循环结束后，没有处理最后一个合并区间

• 正确：应在循环结束后添加 result.push_back({left, right});

为啥还要最后添加 他不是循环能走到最后一个区间吗？

需要在循环结束后额外添加最后一个合并区间，因为循环内部只有在"没有重叠"的情况下才会添加区间。

考虑这个流程：

• 循环中，只有当前区间与前一个区间不重叠时，才会把前一个合并好的区间添加到结果中
• 对于最后一个区间（或最后一组合并的区间），循环结束后不会再有新的区间来判断它是否需要被添加

举个例子，输入 [[1,3], [2,6], [8,10]]：

• 遍历到 [2,6] 时，发现与 [1,3] 重叠，更新 right=6，但不添加任何结果

• 遍历到 [8,10] 时，发现与 [1,6] 不重叠，所以添加 [1,6] 到结果，并更新 left=8, right=10

• 循环结束，如果不加最后一步，结果中只有 [1,6]，缺少了 [8,10]

所以必须在循环结束后额外添加最后处理的那个区间（无论它是单个区间还是合并后的区间），确保所有区间都被包含在结果中。

算法逻辑错误:

• 在你的代码中，即使区间有重叠，也没有正确合并它们

• 正确的合并逻辑是：当有重叠时，更新右边界为两个区间右边界的最大值；只有当没有重叠时，才将当前合并区间添加到结果，并开始新的合并区间

正确写法

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {//先进行初始化判断if(intervals.empty()){return {};}//进行排序sort(intervals.begin(),intervals.end());//这个排序只能保证子区间是从低往高的//初始化双指针int left = intervals[0][0];int right = intervals[0][1];//初始化结果集vector<vector<int>> result;//进行循环比较是否出现重叠for(int i =1;i<intervals.size();i++){if(right >= intervals[i][0])  //说明有重叠的部分{right = max(right,intervals[i][1]);}else{result.push_back({left,right});left = intervals[i][0];right = intervals[i][1];}}result.push_back({left,right});return result;}
};