当前位置：首页 > news >正文

（14）LeetCode 56. 合并区间

news 2026/7/11 2:51:58

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] 被视为重叠区间（闭区间）。

💡 解题思路

核心思想

排序：按照每个区间的左端点升序排序，这样所有区间按起始位置有序排列。
一次遍历合并：
- 用两个变量l和r记录当前合并区间的左右端点。
- 依次检查后续区间：
  - 若当前区间的左端点> r，说明与当前合并区间没有重叠，将当前合并区间存入结果，并更新l和r为新区间的端点。
  - 否则，说明有重叠，更新r = max(r, current_end)，合并区间。
收尾：遍历结束后，将最后一个合并区间加入结果。

为什么排序是关键？

排序后，我们只需从左到右扫描一次，因为左端点递增，任何重叠只可能发生在相邻区间之间，无需回头检查。

重叠判断条件

区间[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]`	保存最后一个区间