文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接56.合并区间2、题目描述二、个人思路整理1、思路分析核心思路排序贪心合并。按左端点排序将所有区间按照起始位置intervals[i][0]升序排序。排序后所有可能重叠的区间都会紧挨在一起。线性扫描合并初始化答案数组merged先放入第一个区间。遍历后续的每个区间[start, end]重叠若start merged.back()[1]说明当前区间与前一个区间重合更新前一个区间的右端点为max(merged.back()[1], end)。不重叠若start merged.back()[1]说明是独立的新区间直接加入merged。2、解题代码classSolution{public:vectorvectorintmerge(vectorvectorintintervals){// 特判如果区间数组为空直接返回空结果if(intervals.empty()){return{};}// 1. 按照区间的左端点进行升序排序// 默认按 vector 的字典序排序即先比较 intervals[i][0]若相同再比较 intervals[i][1]sort(intervals.begin(),intervals.end());vectorvectorintmerged;// 将排序后的第一个区间直接作为初始合并基准merged.push_back(intervals[0]);// 2. 依次遍历后续区间尝试合并for(inti1;iintervals.size();i){intLintervals[i][0],Rintervals[i][1];// 当前区间的左端点 上一个合并区间的右端点说明存在重叠if(Lmerged.back()[1]){// 贪心合并右端点更新为两者的最大值覆盖更广的范围merged.back()[1]max(merged.back()[1],R);}else{// 无重叠当前区间无法与前一个区间合并作为独立的新区间加入结果集merged.push_back(intervals[i]);}}returnmerged;}};2026.10.17重做后补充在C的vector中end()和back()的核心区别在于返回类型和指向的位置完全不同end()返回的是一个迭代器指向容器最后一个元素之后的虚拟位置不存储实际有效元素。back()返回的是一个直接引用直接代表容器中的最后一个实际元素的值。复杂度分析时间复杂度O ( n log n ) O(n \log n)O(nlogn)主要开销在于排序后续单次扫描为O ( n ) O(n)O(n)。空间复杂度O ( log n ) O(\log n)O(logn)或O ( n ) O(n)O(n)取决于排序算法所占用的栈空间。三、知识风暴区间合并是解决区间类问题的核心技巧常与排序配合使用。其基本思想是先将所有区间按左端点排序再依次遍历判断当前区间能否与上一个已合并区间合并从而将重叠区间合并为一个更大的区间。算法核心思想排序预处理按区间左端点升序排序保证后续只需线性扫描即可完成合并。贪心合并维护一个结果集merged依次遍历每个区间若当前区间左端点L merged.back()[1]说明与上一个合并区间重叠更新右端点为max(merged.back()[1], R)否则无重叠将当前区间作为独立新区间加入结果集。状态转移merged.back()[1] max(merged.back()[1], R)算法变体与扩展返回合并后的区间列表本题即要求返回合并后的完整区间集合。插入区间给定一个已排序且不重叠的区间列表插入一个新区间并合并LeetCode 57。区间交集求两个区间列表的交集LeetCode 986。会议室问题判断能否参加所有会议本质是判断区间是否重叠LeetCode 252/253。与其他算法的对比暴力法O(n²)时间复杂度两两比较所有区间对。排序贪心O(n log n)时间复杂度排序后单次线性扫描即可完成合并是最优解。差分数组适用于区间频繁增减的场景但本题只需一次合并排序贪心更直接。相关 LeetCode 例题56. 合并区间本题57. 插入区间在已排序区间中插入新区间并合并986. 区间列表的交集求两个区间列表的交集252. 会议室判断区间是否重叠 
长河君 · 2026/10/18 15:56:49 · 阅读 1.2k 【普通数组】LC 56.合并区间
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接56.合并区间2、题目描述二、个人思路整理1、思路分析核心思路排序贪心合并。按左端点排序将所有区间按照起始位置intervals[i][0]升序排序。排序后所有可能重叠的区间都会紧挨在一起。线性扫描合并初始化答案数组merged先放入第一个区间。遍历后续的每个区间[start, end]重叠若start merged.back()[1]说明当前区间与前一个区间重合更新前一个区间的右端点为max(merged.back()[1], end)。不重叠若start merged.back()[1]说明是独立的新区间直接加入merged。2、解题代码classSolution{public:vectorvectorintmerge(vectorvectorintintervals){// 特判如果区间数组为空直接返回空结果if(intervals.empty()){return{};}// 1. 按照区间的左端点进行升序排序// 默认按 vector 的字典序排序即先比较 intervals[i][0]若相同再比较 intervals[i][1]sort(intervals.begin(),intervals.end());vectorvectorintmerged;// 将排序后的第一个区间直接作为初始合并基准merged.push_back(intervals[0]);// 2. 依次遍历后续区间尝试合并for(inti1;iintervals.size();i){intLintervals[i][0],Rintervals[i][1];// 当前区间的左端点 上一个合并区间的右端点说明存在重叠if(Lmerged.back()[1]){// 贪心合并右端点更新为两者的最大值覆盖更广的范围merged.back()[1]max(merged.back()[1],R);}else{// 无重叠当前区间无法与前一个区间合并作为独立的新区间加入结果集merged.push_back(intervals[i]);}}returnmerged;}};2026.10.17重做后补充在C的vector中end()和back()的核心区别在于返回类型和指向的位置完全不同end()返回的是一个迭代器指向容器最后一个元素之后的虚拟位置不存储实际有效元素。back()返回的是一个直接引用直接代表容器中的最后一个实际元素的值。复杂度分析时间复杂度O ( n log n ) O(n \log n)O(nlogn)主要开销在于排序后续单次扫描为O ( n ) O(n)O(n)。空间复杂度O ( log n ) O(\log n)O(logn)或O ( n ) O(n)O(n)取决于排序算法所占用的栈空间。三、知识风暴区间合并是解决区间类问题的核心技巧常与排序配合使用。其基本思想是先将所有区间按左端点排序再依次遍历判断当前区间能否与上一个已合并区间合并从而将重叠区间合并为一个更大的区间。算法核心思想排序预处理按区间左端点升序排序保证后续只需线性扫描即可完成合并。贪心合并维护一个结果集merged依次遍历每个区间若当前区间左端点L merged.back()[1]说明与上一个合并区间重叠更新右端点为max(merged.back()[1], R)否则无重叠将当前区间作为独立新区间加入结果集。状态转移merged.back()[1] max(merged.back()[1], R)算法变体与扩展返回合并后的区间列表本题即要求返回合并后的完整区间集合。插入区间给定一个已排序且不重叠的区间列表插入一个新区间并合并LeetCode 57。区间交集求两个区间列表的交集LeetCode 986。会议室问题判断能否参加所有会议本质是判断区间是否重叠LeetCode 252/253。与其他算法的对比暴力法O(n²)时间复杂度两两比较所有区间对。排序贪心O(n log n)时间复杂度排序后单次线性扫描即可完成合并是最优解。差分数组适用于区间频繁增减的场景但本题只需一次合并排序贪心更直接。相关 LeetCode 例题56. 合并区间本题57. 插入区间在已排序区间中插入新区间并合并986. 区间列表的交集求两个区间列表的交集252. 会议室判断区间是否重叠