文章目录
- 前言
- 一、题目
- 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:vector<vector<int>>merge(vector<vector<int>>&intervals){// 特判：如果区间数组为空，直接返回空结果if(intervals.empty()){return{};}// 1. 按照区间的左端点进行升序排序// 默认按 vector 的字典序排序，即先比较 intervals[i][0]，若相同再比较 intervals[i][1]sort(intervals.begin(),intervals.end());vector<vector<int>>merged;// 将排序后的第一个区间直接作为初始合并基准merged.push_back(intervals[0]);// 2. 依次遍历后续区间尝试合并for(inti=1;i<intervals.size();i++){intL=intervals[i][0],R=intervals[i][1];// 当前区间的左端点 <= 上一个合并区间的右端点，说明存在重叠if(L<=merged.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. 会议室（判断区间是否重叠）
