LeetCode 56合并区间：排序与贪心-云帆数科

一、题目来源与描述题目来源LeetCode 第 56 题 - 合并区间 (Merge Intervals)难度中等题目描述以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi]。请你合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。二、输入数据结构深度解析在解答本题前我们需要明确输入数据的结构。题目给出的输入 intervals 其实是一个二维数组在 C 中为二维向量vectorvectorint。外层维度表示有多少个区间。例如 intervals.size() 代表区间的总个数。内层维度固定长度为 2。intervals[i][0] 代表第 i 个区间的左端点起始位置intervals[i][1] 代表第 i 个区间的右端点结束位置。示例解析输入intervals [[1,3],[2,6],[8,10],[15,18]]这代表集合中有 4 个区间区间 1从 1 到 3区间 2从 2 到 6区间 3从 8 到 10区间 4从 15 到 18三、核心算法思路排序贪心这道题如果直接两两比较时间复杂度会非常高。最优的解法基于一个关键的预处理步骤排序。1.为什么需要排序如果区间是无序的比如 [[8,10], [1,3], [2,6]]我们很难判断 [1,3] 和 [2,6] 是否重叠因为它们不相邻。但如果我们按区间的左端点进行升序排序数组就会变成 [[1,3], [2,6], [8,10]]。此时我们只需要从左到右遍历一次比较当前区间与前一个已合并区间的关系即可。2.贪心策略与合并逻辑排序后我们维护一个结果数组 merged。遍历排序后的区间对于每一个当前区间 curr与 merged 中的最后一个区间 last 进行比较情况 A发生重叠或相接如果 curr 的左端点≤last 的右端点即 curr[0] last[1]说明两个区间有交集。操作更新 last 的右端点取两者右端点的最大值last[1] max(last[1], curr[1])。(注意这里不需要更新左端点因为我们已经按左端点排序last的左端点一定小于等于curr的左端点)情况 B没有重叠如果 curr 的左端点last 的右端点即 curr[0] last[1]说明两个区间完全分离。操作直接将 curr 加入 merged 数组成为新的 last。3.算法流程图解以 intervals [[1,3],[2,6],[8,10],[15,18]] 为例排序已经是升序。初始化merged [[1,3]]遍历[2,6]2 3 (重叠) - 更新 merged 末尾为 [1, max(3,6)] [1,6]。此时 merged [[1,6]]遍历[8,10]8 6 (不重叠) - 直接加入。此时 merged [[1,6], [8,10]]遍历[15,18]15 10 (不重叠) - 直接加入。此时 merged [[1,6], [8,10], [15,18]]结束返回 merged。四、 C 代码实现class Solution { public: vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vectorvectorint merged; merged.push_back(intervals[0]); for (int i 1; i intervals.size(); i) { int last_right merged.back()[1]; int curr_left intervals[i][0]; int curr_right intervals[i][1]; if (curr_left last_right) { merged.back()[1] max(last_right, curr_right); } else { merged.push_back(intervals[i]); } } return merged; } };五、复杂度分析时间复杂度O(NlogN)主要消耗在排序上C 的 std::sort 平均时间复杂度为O(NlogN)。遍历合并的过程只需要一次线性扫描时间复杂度为O(N)。总体时间复杂度为O(NlogN)其中N是区间的数量。空间复杂度O(logN)或O(N)如果不考虑返回结果所占用的空间主要取决于排序算法的递归栈空间通常为O(logN)。如果考虑返回结果 merged 数组最坏情况下所有区间都不重叠需要存储N个区间空间复杂度为O(N)。

企业数字化 ERP 产品动态

相关推荐

「2022 年」崔庆才 Python3 网络爬虫学习教程

大家好, 我是崔庆才, 大家能够在这里相见, 我对此感到非常高兴。不管您之前对于爬虫技术有没有涉猎过, 或者说您目前是刚刚开始学习爬虫。我都盼望着我亲手所写作的这部关于爬虫的系统性系列教程文本, 最终能够为各位读者朋友们的工作与学习带来一定程度的实际帮助价值。如果要… · 2026/9/27 22:59:29

C语言小白的自传

大家好，我是一名20岁、湖北某高校计算机应用技术专业大二学生。这段时间系统入门了C语言，从零基础看不懂代码，到能掌握基础语法、运算逻辑、输出规则，算是真正踏进了计算机专业的大门，在这里简单记录一下我的学习收获和… · 2026/9/27 22:59:29

SpringBoot实战：从0到1搭建高并发秒杀系统

数据库设计：别让库存字段成为瓶颈商品表里库存字段用int，扣减时update stock stock - 1 where id ? and stock > 0，利用数据库行锁保证不超卖。但这条SQL在并发下会串行执行，QPS上限就是单行锁的吞吐量，撑死几百… · 2026/9/27 22:59:29

QwenImageEdit与ComfyUI搭建人物一致性写真工作流

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:29:29