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:vectorvectorintmerge(vectorvectorintintervals){vectorvectorintres;// 存储合并后的结果if(intervals.empty())returnres;// 处理空输入// 1. 按区间左端点排序sort(intervals.begin(),intervals.end());// 2. 初始化当前合并区间intlintervals[0][0],rintervals[0][1];// 3. 遍历后续区间for(inti1;iintervals.size();i){if(intervals[i][0]r){// 无重叠res.push_back({l,r});// 保存当前合并区间lintervals[i][0];// 开始新区间rintervals[i][1];}else{// 有重叠rmax(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})将合并好的区间存入结果注意用{}初始化vectorintr 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]从第一个区间开始i1[2,6][1, 3]→[1, 6]重叠扩展r6i2[8,10][1, 6]无重叠保存[1,6]新合并区间[8,10]i3[15,18][8,10]无重叠保存[8,10]新合并区间[15,18]结束-[15,18]保存最后一个区间最终结果[[1,6],[8,10],[15,18]]⚠️ 注意事项输入区间是闭区间因此[1,2]和[2,3]视为重叠合并为[1,3]。排序是必须的否则无法通过一次遍历判断所有重叠。处理空输入时直接返回空数组避免访问越界。
（14）LeetCode 56. 合并区间
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:vectorvectorintmerge(vectorvectorintintervals){vectorvectorintres;// 存储合并后的结果if(intervals.empty())returnres;// 处理空输入// 1. 按区间左端点排序sort(intervals.begin(),intervals.end());// 2. 初始化当前合并区间intlintervals[0][0],rintervals[0][1];// 3. 遍历后续区间for(inti1;iintervals.size();i){if(intervals[i][0]r){// 无重叠res.push_back({l,r});// 保存当前合并区间lintervals[i][0];// 开始新区间rintervals[i][1];}else{// 有重叠rmax(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})将合并好的区间存入结果注意用{}初始化vectorintr 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]从第一个区间开始i1[2,6][1, 3]→[1, 6]重叠扩展r6i2[8,10][1, 6]无重叠保存[1,6]新合并区间[8,10]i3[15,18][8,10]无重叠保存[8,10]新合并区间[15,18]结束-[15,18]保存最后一个区间最终结果[[1,6],[8,10],[15,18]]⚠️ 注意事项输入区间是闭区间因此[1,2]和[2,3]视为重叠合并为[1,3]。排序是必须的否则无法通过一次遍历判断所有重叠。处理空输入时直接返回空数组避免访问越界。
