LeetCode 热题 100-----14.合并区间-编程阁

一、题目详解

首先，我们用最直白的话把题目说清楚，不用任何专业术语，保证你一看就懂：

给你一个“区间数组”，这个数组里的每一个元素，都是一个“区间”——比如 [1,3]，它代表从数字1到数字3的所有数（包括1和3），你可以把它想象成一根从1到3的线段。

这些线段可能会有三种情况：

重叠：比如 [1,3] 和 [2,6]，线段[2,6]的开头（2）在[1,3]的中间，两个线段叠在一起，能拼成一根更长的线段 [1,6]；
端点相连：比如 [1,4] 和 [4,5]，第一个线段的结尾（4）和第二个线段的开头（4）连在一起，也算“能合并”，拼成 [1,5]；
完全不重叠：比如 [8,10] 和 [15,18]，两个线段离得很远，没法合并，只能保留原样。

你的任务就是：把所有能合并的线段（重叠、端点相连）都合并成一根长线段，最后返回一个“没有重叠、没有相连”的线段数组，并且这组线段要能完全覆盖原来所有的线段，一个都不能漏。

举个生活例子：你有几张纸条，分别写着1-3、2-6、8-10、15-18，把重叠/相连的纸条粘在一起，最后就剩下3张：1-6、8-10、15-18，这就是题目要的结果。

二、必备前置知识

在看解题思路和代码前，必须先掌握这几个基础知识点——哪怕你完全没学过编程，看完这部分也能跟上，每一个点都配例子，不跳步！

2.1 什么是“区间”和“区间数组”

① 区间：就是两个数字组成的“范围”，格式是 [起点, 终点]，比如 [1,3]，起点是1，终点是3，且永远满足“起点 ≤ 终点”（题目提示里明确说了 0 ≤ starti ≤ endi ≤ 104）；

② 区间数组：就是存放多个区间的“容器”，比如题目里的输入 intervals = [[1,3],[2,6],[8,10],[15,18]]，这是一个“二维数组”（可以理解成“数组里套数组”）：

- Python里叫“列表套列表”，写法是 List[List[int]]，外面的大列表是“区间的集合”，里面的每个小列表是“单个区间”；

- C++里叫“vector套vector”，写法是 vector<vector<int>>，和Python的列表套列表功能完全一样，都是用来存多个区间的。

举例子：intervals = [[1,4],[4,5]]，这个区间数组里有2个区间，第一个区间是 [1,4]，第二个是 [4,5]。

2.2 二维数组（列表）的访问方式

我们要操作区间，就得先学会“拿到”某个区间，以及某个区间的“起点”和“终点”，两种语言的访问方式如下（重点记，代码里天天用）：

① Python（列表套列表）：

- 拿到第i个区间：intervals[i]（i从0开始，比如intervals[0]就是第一个区间）；

- 拿到第i个区间的起点：intervals[i][0]（第一个[]是“第i个区间”，第二个[]是“区间的第0个元素=起点”）；

- 拿到第i个区间的终点：intervals[i][1]（第二个[]是“区间的第1个元素=终点”）；

例子：intervals = [[1,3],[2,6]]，intervals[0][0] = 1（第一个区间的起点），intervals[1][1] = 6（第二个区间的终点）。

② C++（vector套vector）：

- 拿到第i个区间：intervals[i]（和Python一样，i从0开始）；

- 拿到第i个区间的起点：intervals[i][0]（写法和Python完全一样）；

- 拿到第i个区间的终点：intervals[i][1]（写法和Python完全一样）；

例子：vector<vector<int>> intervals = {{1,3},{2,6}}; ，intervals[0][0] = 1，intervals[1][1] = 6。

2.3 排序的作用（核心中的核心）

这道题的关键一步就是“排序”，为什么要排序？举个例子你就懂：

假设输入是 [[4,7],[1,4]]（示例3），这两个区间是乱序的（第一个区间起点4，第二个起点1），如果不排序，我们先看[4,7]，再看[1,4]，容易判断错；

但如果我们按“区间的起点从小到大”排序，这个数组就变成了 [[1,4],[4,7]]，此时重叠/相连的区间就“挨在一起”了——我们只需要逐个检查相邻的两个区间，就能判断是否能合并，大大简化难度。

总结：排序的目的，是让所有“可能能合并”的区间（重叠、相连）都变成相邻的，这样我们只需要遍历一次，就能完成所有合并，不用来回找。

补充：Python和C++都有现成的排序函数，不用我们自己写，后面代码里会详细讲怎么用。

2.4 容器的基本操作（存结果用）

我们需要一个“新容器”来存合并后的区间，这个容器也是二维数组（列表/vector），常用操作如下：

① Python（列表）：

创建空列表：merged = []（merged就是我们存结果的容器）；
往列表里加元素（加一个区间）：merged.append(区间)，比如 merged.append([1,3])，此时merged就变成了 [[1,3]]；
取列表的最后一个元素（最后一个合并好的区间）：merged[-1]，比如merged是 [[1,6],[8,10]]，merged[-1]就是 [8,10]；
修改列表最后一个元素的终点：merged[-1][1] = 新终点，比如merged[-1]是 [1,3]，执行 merged[-1][1] = 6，就变成了 [1,6]。

② C++（vector）：

创建空vector：vector<vector<int>> merged;（和Python的空列表一样）；
往vector里加元素：merged.push_back(区间)，比如 merged.push_back({1,3})，此时merged就有一个区间 [1,3]；
取vector的最后一个元素：merged.back()，比如merged是 {{1,6},{8,10}}，merged.back()就是 {8,10}；
判断vector是否为空：merged.empty()，为空返回true，不为空返回false（用来判断是否是第一个区间）；
修改最后一个元素的终点：merged.back()[1] = 新终点，和Python的 merged[-1][1] 用法一样。

2.5 循环遍历（逐个检查区间）

我们需要逐个检查每个原始区间，判断它能不能和“已经合并好的最后一个区间”合并，这就需要用到“循环遍历”：

① Python：用 for 循环遍历区间数组，写法是 for current in intervals: ，其中current就是“当前正在检查的区间”；

例子：intervals = [[1,3],[2,6]]，循环第一次current是 [1,3]，第二次是 [2,6]。

② C++：用 for 循环遍历，写法是 for (auto& current : intervals) ，其中auto是“自动识别类型”（不用我们写vector<int>），&是“引用”（相当于直接操作原区间，不复制，更高效），current也是“当前正在检查的区间”。

2.6 补充：max函数（取两个数的最大值）

合并区间时，需要取“两个区间终点的最大值”作为合并后区间的终点，比如 [1,3] 和 [2,6]，终点分别是3和6，max(3,6)=6，所以合并后终点是6。

① Python：max(a, b)，直接用，比如 max(3,6) → 6；

② C++：max(a, b)，需要包含头文件 #include <algorithm>（后面代码会包含），比如 max(3,6) → 6。

三、解题思路（由易到难：暴力解法→最优解法）

我们先讲“暴力解法”（容易理解，思路简单），再讲“最优解法”（面试/刷题常用，效率高），对比两者的区别，让你明白为什么最优解法更好。

3.1 暴力解法（思路简单，效率低）

3.1.1 核心思路（4步）

暴力解法的核心是“两两比较”，把所有能合并的区间都合并，直到没有可合并的区间为止：

先给区间数组按“起点升序”排序（和最优解法一样，排序是基础）；
创建一个新容器，把原始区间数组的所有元素都放进去（相当于“待合并的区间”）；
循环遍历新容器，拿当前区间和它后面的所有区间比较：
1. 如果当前区间和后面某个区间重叠/相连 → 合并这两个区间，把合并后的区间放回当前位置，删除后面那个区间；
2. 如果不重叠 → 继续比较下一个。
重复步骤3，直到遍历完所有区间，没有可合并的为止，最后返回这个新容器。

3.1.2 暴力解法的问题

因为要“两两比较”，比如有n个区间，最坏情况下（所有区间都不重叠），需要比较n*(n-1)/2次，时间复杂度是 O(n²)（n平方），当n很大时（比如题目提示的n=104），会很慢，所以面试时不推荐用，但可以通过它理解“合并”的逻辑。

3.2 最优解法（排序+一次遍历，效率高）

这是面试和刷题的“标准答案”，时间复杂度最低，代码最简单，也是我们重点讲解的解法，核心思路是“排序后，只和最后一个合并好的区间比较”，不用两两比较。

3.2.1 核心思路

排序：将所有区间按“起点从小到大”排序（和暴力解法第一步一样，核心目的是让重叠/相连的区间相邻）；
初始化：创建一个空容器merged，用来存合并后的区间（一开始是空的，没有任何合并好的区间）；
遍历判断（核心步骤）：逐个取出原始区间（current），和merged里“最后一个合并好的区间”（last）比较：
1. 如果merged是空的（还没有任何合并好的区间）→ 直接把current加进去（第一个区间没有可合并的对象）；
2. 如果last的终点 ≥ current的起点 → 重叠/相连，需要合并：把last的终点改成“last的终点和current的终点的最大值”（比如last是[1,3]，current是[2,6]，last的终点改成max(3,6)=6，合并成[1,6]）；
3. 如果last的终点 < current的起点 → 不重叠，直接把current加到merged里（和前面的区间都不重叠，作为新的合并区间）；
返回结果：遍历完所有原始区间后，merged里就是“没有重叠、完全覆盖所有原始区间”的结果，返回merged即可。

3.2.2 最优解法的优势

排序的时间复杂度是 O(n log n)（n乘以log n），遍历的时间复杂度是 O(n)（只走一遍），整体时间复杂度是 O(n log n)，比暴力解法的 O(n²) 快很多，适合n很大的情况（比如题目中的104个区间），也是面试中必须掌握的解法。

3.2.3 思路演示（结合示例1，跟着算）

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

排序：已经是按起点升序，不用变 → [[1,3],[2,6],[8,10],[15,18]]；
初始化：merged = []；
遍历第一个区间 current = [1,3]：merged是空的，直接加进去 → merged = [[1,3]]；
遍历第二个区间 current = [2,6]：last = [1,3]，last[1]（3）≥ current[0]（2）→ 合并，last[1] = max(3,6)=6 → merged = [[1,6]]；
遍历第三个区间 current = [8,10]：last = [1,6]，last[1]（6）< current[0]（8）→ 不合并，加进去 → merged = [[1,6],[8,10]]；
遍历第四个区间 current = [15,18]：last = [8,10]，last[1]（10）< current[0]（15）→ 不合并，加进去 → merged = [[1,6],[8,10],[15,18]]；
返回merged，就是示例1的输出。

四、Python 完整代码（含主函数+详细注释+运行流程+测试用例）

以下代码可直接复制运行（本地Python环境、LeetCode均可），每一句都有注释，并且包含“主函数”——可以测试题目给的3个示例，还能自定义输入，打印输入和输出，能清晰看到代码运行过程。

4.1 完整代码（最优解法，面试推荐）

# 导入类型提示（LeetCode默认自带，本地Python运行时，没有这句话会报警告，但不影响运行） from typing import List # 定义Solution类（LeetCode固定格式，必须有这个类，里面放解题函数） class Solution: # 定义merge函数（题目要求的函数名，参数是intervals，类型是List[List[int]]，返回值也是List[List[int]]） def merge(self, intervals: List[List[int]]) -> List[List[int]]: # 第一步：按区间的【起点】从小到大排序（Python默认对二维列表按第一个元素排序，完美符合我们的需求） # 比如输入[[4,7],[1,4]]，排序后变成[[1,4],[4,7]] intervals.sort() # 第二步：初始化结果容器merged，用来存合并后的区间，一开始是空列表 merged = [] # 第三步：遍历每一个原始区间，current就是当前正在检查的区间 for current in intervals: # 情况1：merged是空的（还没有任何合并好的区间）→ 直接把当前区间加进去 if not merged: merged.append(current) else: # 情况2：merged不是空的，取出merged里最后一个合并好的区间（last） last = merged[-1] # 判断：last的终点 ≥ current的起点 → 重叠/相连，需要合并 if last[1] >= current[0]: # 合并逻辑：把last的终点改成“last的终点和current的终点的最大值” # 比如last是[1,3]，current是[2,6]，max(3,6)=6，last变成[1,6] merged[-1][1] = max(last[1], current[1]) else: # 情况3：不重叠，直接把当前区间加到merged里 merged.append(current) # 第四步：返回合并后的结果 return merged # 主函数（核心！用来测试代码，可以在这里修改输入，查看运行结果） if __name__ == "__main__": # 1. 创建Solution类的实例（必须创建实例，才能调用里面的merge函数） solution = Solution() # 2. 测试题目给出的3个示例 print("="*50) print("测试示例1：") intervals1 = [[1,3],[2,6],[8,10],[15,18]] # 示例1输入 result1 = solution.merge(intervals1) # 调用merge函数，得到结果 print(f"输入：{intervals1}") print(f"输出：{result1}") # 预期输出：[[1,6],[8,10],[15,18]] print("="*50) print("测试示例2：") intervals2 = [[1,4],[4,5]] # 示例2输入 result2 = solution.merge(intervals2) print(f"输入：{intervals2}") print(f"输出：{result2}") # 预期输出：[[1,5]] print("="*50) print("测试示例3：") intervals3 = [[4,7],[1,4]] # 示例3输入 result3 = solution.merge(intervals3) print(f"输入：{intervals3}") print(f"输出：{result3}") # 预期输出：[[1,7]] # 3. 自定义测试用例（可以自己改这里的输入，测试不同情况） print("="*50) print("自定义测试用例1：单个区间（边界情况）") intervals4 = [[5,7]] # 自定义输入：只有1个区间 result4 = solution.merge(intervals4) print(f"输入：{intervals4}") print(f"输出：{result4}") # 预期输出：[[5,7]] print("="*50) print("自定义测试用例2：完全重叠的区间") intervals5 = [[1,5],[2,3],[4,6]] # 自定义输入：3个区间，全部重叠 result5 = solution.merge(intervals5) print(f"输入：{intervals5}") print(f"输出：{result5}") # 预期输出：[[1,6]] print("="*50) print("自定义测试用例3：乱序且多重叠区间") intervals6 = [[3,5],[1,2],[4,7],[6,8]] # 自定义输入：乱序，多个重叠 result6 = solution.merge(intervals6) print(f"输入：{intervals6}") print(f"输出：{result6}") # 预期输出：[[1,2],[3,8]]

4.2 代码运行流程拆解（跟着走，一步都不跳）

我们以“自定义测试用例3”为例，拆解代码运行的每一步，让你清楚每一句代码的作用：

自定义测试用例3输入：intervals6 = [[3,5],[1,2],[4,7],[6,8]]

运行 intervals.sort() → 按起点排序，排序后变成 [[1,2],[3,5],[4,7],[6,8]]；
merged = [] → 初始化空列表；
第一次循环，current = [1,2]：
1. merged是空的 → 执行 merged.append([1,2]) → merged = [[1,2]]；
第二次循环，current = [3,5]：
1. merged不是空的，last = merged[-1] = [1,2]；
2. 判断 last[1]（2）≥ current[0]（3）？→ 2 < 3，不成立；
3. 执行 merged.append([3,5]) → merged = [[1,2],[3,5]]；
第三次循环，current = [4,7]：
1. last = [3,5]；
2. 判断 last[1]（5）≥ current[0]（4）？→ 成立，重叠；
3. merged[-1][1] = max(5,7) =7 → merged变成 [[1,2],[3,7]]；
第四次循环，current = [6,8]：
1. last = [3,7]；
2. 判断 last[1]（7）≥ current[0]（6）？→ 成立，重叠；
3. merged[-1][1] = max(7,8) =8 → merged变成 [[1,2],[3,8]]；
循环结束，返回 merged → [[1,2],[3,8]]，和预期输出一致。

4.3 Python 暴力解法代码（可选，理解用）

from typing import List class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: # 第一步：排序（暴力解法也需要排序，否则没法两两比较） intervals.sort() # 第二步：把原始区间全部放进merged，作为待合并的容器 merged = intervals.copy() # 复制一份，不修改原始输入 # 第三步：两两比较，合并重叠区间（i从0开始，遍历到倒数第二个区间） i = 0 while i < len(merged) - 1: # 当前区间 current = merged[i] # 下一个区间（和current比较） next_interval = merged[i+1] # 判断是否重叠/相连 if current[1] >= next_interval[0]: # 合并两个区间，起点是current的起点，终点是两者终点的最大值 merged[i] = [current[0], max(current[1], next_interval[1])] # 删除下一个区间（已经合并到current里了） del merged[i+1] # 注意：删除后，i不用+1（因为下一个区间变成了原来的i+2，需要重新比较当前i） else: # 不重叠，i+1，比较下一对 i += 1 return merged # 主函数（和最优解法的主函数一样，可直接测试） if __name__ == "__main__": solution = Solution() intervals = [[3,5],[1,2],[4,7],[6,8]] print(f"输入：{intervals}") print(f"输出：{solution.merge(intervals)}") # 输出：[[1,2],[3,8]]

五、C++ 完整代码（含主函数+详细注释+运行流程+测试用例）

以下代码可直接复制到C++编译器（比如Dev-C++、VS）运行，同样包含主函数、测试用例，每一句都有注释，和Python代码逻辑完全一致，只是语法不同，可以对照Python代码看，更容易理解。

5.1 完整代码（最优解法，面试推荐）

#include <iostream> // 用于输入输出（打印测试用例） #include <vector> // 用于使用vector容器（存区间数组） #include <algorithm> // 用于使用sort排序函数和max函数 using namespace std; // 简化代码，不用每次都写std:: // 定义Solution类（LeetCode固定格式） class Solution { public: // 定义merge函数（题目要求的函数，参数是vector<vector<int>>& intervals，引用传递，更高效） // 返回值是vector<vector<int>>，即合并后的区间数组 vector<vector<int>> merge(vector<vector<int>>& intervals) { // 第一步：按区间起点升序排序 // sort函数的参数：容器的起始迭代器、结束迭代器，默认按第一个元素升序排序 sort(intervals.begin(), intervals.end()); // 第二步：初始化结果容器merged，空vector vector<vector<int>> merged; // 第三步：遍历每一个原始区间，auto& current自动识别类型，引用传递 for (auto& current : intervals) { // 情况1：merged为空（没有合并好的区间），直接添加当前区间 if (merged.empty()) { merged.push_back(current); } else { // 情况2：merged不为空，取出最后一个合并好的区间（引用传递，修改会直接生效） auto& last = merged.back(); // 判断：last的终点 ≥ current的起点 → 重叠/相连，合并 if (last[1] >= current[0]) { // 合并逻辑：更新last的终点为两者的最大值 last[1] = max(last[1], current[1]); } else { // 情况3：不重叠，直接添加当前区间 merged.push_back(current); } } } // 第四步：返回合并后的结果 return merged; } }; // 主函数（测试代码，可修改输入） int main() { // 1. 创建Solution类的实例 Solution solution; // 2. 测试题目给出的3个示例 cout << "======================" << endl; cout << "测试示例1：" << endl; vector<vector<int>> intervals1 = {{1,3},{2,6},{8,10},{15,18}}; // 示例1输入 vector<vector<int>> result1 = solution.merge(intervals1); // 调用merge函数 cout << "输入："; // 打印输入的区间数组（循环遍历打印） for (int i = 0; i < intervals1.size(); i++) { cout << "[" << intervals1[i][0] << "," << intervals1[i][1] << "]"; if (i != intervals1.size() - 1) cout << ","; } cout << endl; cout << "输出："; // 打印结果 for (int i = 0; i < result1.size(); i++) { cout << "[" << result1[i][0] << "," << result1[i][1] << "]"; if (i != result1.size() - 1) cout << ","; } cout << endl; cout << "======================" << endl; cout << "测试示例2：" << endl; vector<vector<int>> intervals2 = {{1,4},{4,5}}; vector<vector<int>> result2 = solution.merge(intervals2); cout << "输入："; for (int i = 0; i < intervals2.size(); i++) { cout << "[" << intervals2[i][0] << "," << intervals2[i][1] << "]"; if (i != intervals2.size() - 1) cout << ","; } cout << endl; cout << "输出："; for (int i = 0; i < result2.size(); i++) { cout << "[" << result2[i][0] << "," << result2[i][1] << "]"; if (i != result2.size() - 1) cout << ","; } cout << endl; cout << "======================" << endl; cout << "测试示例3：" << endl; vector<vector<int>> intervals3 = {{4,7},{1,4}}; vector<vector<int>> result3 = solution.merge(intervals3); cout << "输入："; for (int i = 0; i < intervals3.size(); i++) { cout << "[" << intervals3[i][0] << "," << intervals3[i][1] << "]"; if (i != intervals3.size() - 1) cout << ","; } cout << endl; cout << "输出："; for (int i = 0; i < result3.size(); i++) { cout << "[" << result3[i][0] << "," << result3[i][1] << "]"; if (i != result3.size() - 1) cout << ","; } cout << endl; // 3. 自定义测试用例（可修改） cout << "======================" << endl; cout << "自定义测试用例1：单个区间" << endl; vector<vector<int>> intervals4 = {{5,7}}; vector<vector<int>> result4 = solution.merge(intervals4); cout &lt;&lt; "输入："; for (int i = 0; i < intervals4.size(); i++) { cout << "[" << intervals4[i][0] << "," << intervals4[i][1] << "]"; if (i != intervals4.size() - 1) cout << ","; } cout << endl; cout &lt;&lt; "输出："; for (int i = 0; i < result4.size(); i++) { cout << "[" << result4[i][0] << "," << result4[i][1] << "]"; if (i != result4.size() - 1) cout << ","; } cout << endl; cout << "======================" << endl; cout << "自定义测试用例2：完全重叠区间" << endl; vector<vector<int>> intervals5 = {{1,5},{2,3},{4,6}}; vector<vector<int>> result5 = solution.merge(intervals5); cout << "输入："; for (int i = 0; i < intervals5.size(); i++) { cout << "[" << intervals5[i][0] << "," << intervals5[i][1] << "]"; if (i != intervals5.size() - 1) cout << ","; } cout << endl; cout << "输出："; for (int i = 0; i < result5.size(); i++) { cout << "[" << result5[i][0] << "," << result5[i][1] << "]"; if (i != result5.size() - 1) cout << ","; } cout << endl; return 0; // 主函数结束，返回0表示运行成功 }

5.2 代码运行流程拆解（对照Python，易懂）

同样以“自定义测试用例2：完全重叠区间”为例，输入 intervals5 = {{1,5},{2,3},{4,6}}，拆解运行步骤：

运行 sort(intervals.begin(), intervals.end()) → 排序后还是 [[1,5],[2,3],[4,6]]（已经按起点升序）；
merged 初始化为空 vector；
第一次遍历，current = {1,5}：
1. merged.empty() → true（空），执行 merged.push_back(current) → merged = {{1,5}}；
第二次遍历，current = {2,3}：
1. merged不为空，last = merged.back() = {1,5}；
2. 判断 last[1]（5）≥ current[0]（2）→ 成立，合并；
3. last[1] = max(5,3) =5 → merged还是 {{1,5}}；
第三次遍历，current = {4,6}：
1. last = {1,5}；
2. 判断 last[1]（5）≥ current[0]（4）→ 成立，合并；
3. last[1] = max(5,6) =6 → merged变成 {{1,6}}；
遍历结束，返回 merged → {{1,6}}，和预期输出一致。

5.3 C++ 暴力解法代码（可选，理解用）

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { // 第一步：排序 sort(intervals.begin(), intervals.end()); // 第二步：复制原始区间到merged，作为待合并容器 vector<vector<int>> merged = intervals; // 第三步：两两比较，合并重叠区间 int i = 0; while (i < merged.size() - 1) { vector<int> current = merged[i]; vector<int> next_interval = merged[i+1]; if (current[1] >= next_interval[0]) { // 合并区间 merged[i] = {current[0], max(current[1], next_interval[1])}; // 删除下一个区间（erase函数：参数是迭代器，merged.begin() + i+1 是下一个区间的位置） merged.erase(merged.begin() + i + 1); } else { i++; } } return merged; } }; // 主函数测试 int main() { Solution solution; vector<vector<int>> intervals = {{3,5},{1,2},{4,7},{6,8}}; vector<vector<int>> result = solution.merge(intervals); cout << "输入："; for (int i = 0; i < intervals.size(); i++) { cout << "[" << intervals[i][0] << "," << intervals[i][1] << "]"; if (i != intervals.size() - 1) cout << ","; } cout << endl; cout << "输出："; for (int i = 0; i < result.size(); i++) { cout << "[" << result[i][0] << "," << result[i][1] << "]"; if (i != result.size() - 1) cout << ","; } cout << endl; return 0; }

六、复杂度分析

6.1 最优解法复杂度（重点记）

时间复杂度：O(n log n)
- 排序的时间：O(n log n)（这是排序的固定时间复杂度，比如n=104，log n≈17，n log n≈1700，很快）；
- 遍历的时间：O(n)（只遍历一次所有区间，n个区间就走n步）；
- 整体时间由排序决定，所以是 O(n log n)，效率很高，能处理题目中104个区间的最大情况。
空间复杂度：O(n)
- 我们用了一个merged容器来存结果，最坏情况下（所有区间都不重叠），merged的大小和原始区间数组一样，都是n，所以空间复杂度是O(n)；
- 如果不算存结果的容器，排序本身需要的空间是O(1)（Python的sort是原地排序，C++的sort也是原地排序）。

6.2 暴力解法复杂度

时间复杂度：O(n²)（两两比较，最坏情况下要比较n*(n-1)/2次，n=104时，就是104*103/2≈5356次，比最优解法慢很多）；
空间复杂度：O(n)（和最优解法一样，存结果需要O(n)空间）。

七、常见问题&注意事项（避坑）

坑1：忘记排序 → 会导致重叠区间不相邻，合并失败（比如示例3，不排序的话，[[4,7],[1,4]]会判断成不重叠，返回原数组，错误）；
坑2：合并时只改起点，不改终点 → 合并区间的核心是“取终点的最大值”，比如[1,3]和[2,6]，只改起点会变成[1,3]，错误；
坑3：把“端点相连”当成不重叠 → 题目明确说明[1,4]和[4,5]可以合并，所以判断条件是“last[1] ≥ current[0]”，不是“last[1] > current[0]”；
坑4：C++忘记包含头文件 → 比如忘记包含<algorithm>，会导致sort函数、max函数报错；忘记包含<vector>，会导致vector容器无法使用；忘记包含<iostream>，会导致cout、cin无法使用，解决方法：直接复制代码中的3个头文件，不要遗漏；
坑5：Python中修改merged[-1]时出错 → 比如误写为merged[1][1]，这里要注意：merged[-1]才是“最后一个合并好的区间”，merged[1]是固定的第二个区间，当merged只有1个区间时，merged[1]会报错，一定要用merged[-1]；
坑6：忽略“空区间数组”边界情况 → 比如输入intervals = []（空数组，没有任何区间），此时merged也是空的，直接返回即可，代码无需额外修改（当前代码已兼容，merged.empty()会直接成立，不执行后续操作，返回空列表/vector）；
坑7：Python中用“intervals = intervals.sort()” → 错误！Python的sort()方法是“原地排序”，执行后返回None，正确写法是直接写intervals.sort()，不要赋值给原变量，否则intervals会变成None，后续遍历会报错；
坑8：C++中遍历用“auto current”而非“auto& current” → 不用引用的话，会复制每个区间，虽然不影响结果，但效率更低，尤其是区间数量较多时，推荐用auto& current（引用传递）；
坑9：合并后忘记返回结果 → 代码最后一定要return merged，否则函数会返回空值，导致测试用例输出错误；
坑10：容易混淆“区间的起点和终点” → 记住：区间[start, end]，start是第一个元素（index=0），end是第二个元素（index=1），不要写反（比如把current[0]当成终点，current[1]当成起点，会导致判断完全错误）。

八、总结（必看，快速掌握核心）

排序是前提：必须按区间“起点”从小到大排序，让重叠/相连的区间相邻，这是所有解法的基础；

这道题的核心非常简单，记住3句话，就能轻松搞定所有情况，哪怕是也能快速上手：

代码是模板：Python和C++的最优解法代码可以直接记下来，面试时遇到类似题目，稍作修改就能用（比如区间按终点排序、合并区间去重等变种题）。
合并是核心：遍历所有区间，只和“最后一个合并好的区间”比较，重叠/相连就合并（取终点最大值），不重叠就新增。

LeetCode 热题 100-----14.合并区间