1. 项目概述从一道蓝桥杯真题看区间覆盖问题的实战解法最近在整理蓝桥杯的算法训练题翻到了ALGO-986 “藏匿的刺客”。这道题在各大OJ平台和蓝桥杯备考圈里讨论度不低它本质上是一个经典的“区间覆盖”问题但披上了一层有趣的故事外衣。题目大意是有若干个刺客在题目中表现为数轴上的线段区间你需要找出最少的“监视点”使得每个区间内至少有一个点被覆盖。听起来是不是有点像安排哨兵站岗或者给一系列会议安排最少会议室的问题没错这类问题在算法面试和竞赛中非常常见是贪心算法的经典应用场景。我之所以想专门聊聊这道题是因为它在理解贪心策略的“为什么”上非常有代表性。很多初学者在学贪心时总觉得“这策略看起来对但怎么证明呢”或者“为什么按左端点排序不行非得按右端点排序”。通过“藏匿的刺客”这道题我们可以把区间覆盖、区间选点这些问题的底层逻辑彻底掰开揉碎讲清楚。无论你是正在备战蓝桥杯的C/C语言选手还是单纯想巩固一下贪心算法这篇文章都会带你从问题本质出发一步步推导出最优解并分享一些我调试和优化这类代码的实战心得。2. 问题本质与数学模型抽象2.1 题目重述与核心诉求我们先抛开“刺客”这个背景把问题还原到最纯粹的数学模型。假设我们有一组区间每个区间由两个整数[Li, Ri]表示代表刺客可能藏匿的范围。我们的目标是在数轴上选择尽可能少的点使得每一个区间内都至少包含一个我们选择的点。举个例子假设区间是[1, 3],[2, 5],[3, 6]。如果我们把点选在位置3那么它同时落在了三个区间内我们只需要1个点就满足了所有区间。如果区间是[1, 2]和[3, 4]由于它们没有重叠我们至少需要2个点比如在1.5和3.5各放一个。所以问题的核心诉求非常明确最小化点的数量实现对所有区间的覆盖。在算法领域这被称为“区间选点问题”或“最小点覆盖问题”。2.2 贪心策略的直觉与严谨思考为什么这个问题可以用贪心算法解决贪心算法的核心是“每一步都做出当前看来最优的选择”并希望这样的局部最优能导致全局最优。对于区间覆盖一个很自然的想法是“既然要覆盖所有区间那我应该优先把点放在能覆盖最多区间的位置。” 这个位置往往就是多个区间重叠最深的地方。如何找到这个“重叠最深”的地方呢有两种常见的排序思路按区间左端点升序排序直觉上我们从左到右处理区间尽量把点往右放让它能覆盖后面更多的区间。但这里有个陷阱如果第一个区间很长覆盖了后面很多区间但把点放在它很靠右的位置可能会错过一些结束很早的区间。按区间右端点升序排序这是被证明正确的策略。其思想是为了覆盖一个区间点放在这个区间内的任何位置都可以。但为了让它有潜力覆盖后续更多的区间我们应该把它放在尽可能靠右的位置不对恰恰相反应该放在尽可能靠左的、但仍能覆盖当前区间的位置也就是当前区间的右端点。因为右端点是这个区间能“够到”的最远位置如果连当前区间的右端点都无法覆盖某个后续区间那么放在当前区间内更靠左的位置也同样无法覆盖。反之把点放在当前区间的右端点为当前区间提供了覆盖同时这个点因为位置相对靠右相对于本区间它更有可能也落在后面那些右端点更靠后的区间里。让我们严谨地推演一下按右端点排序的贪心策略将所有区间按照右端点从小到大进行排序。初始化一个变量last_point记录上一个放置的点的位置。初始化为一个非常小的数比如负无穷。从左到右遍历排序后的区间。对于当前区间[L, R]如果last_point小于L说明上一个放置的点无法覆盖当前区间因为当前区间的左端点都在上一个点的右边。那么我们必须在当前区间内新放置一个点。为了最大化这个点的效用我们把它放在当前区间的右端点R。然后更新last_point R。如果last_point大于等于L说明上一个放置的点已经落在当前区间内因为当前区间左端点Llast_point 当前区间右端点R这里需要确认last_point是上一个区间的右端点它可能大于当前区间的右端点吗排序后当前区间的右端点R_curr是大于等于上一个区间的右端点last_point的。所以条件last_point L成立时last_point一定小于等于R_curr吗不一定last_point是上一个区间的右端点它可能大于当前区间的右端点。例如区间[1, 10]和[2, 3]按右端点排序后是[2, 3],[1, 10]。处理第一个区间后last_point3。处理第二个区间[1, 10]时L1因为3 1我们认为点3已经覆盖了区间[1,10]这显然是正确的。所以判断条件应该是last_point L才需要新增点。如果last_point L无论last_point是否大于R点last_point都已经在区间[L, R]内了吗不对如果last_point R点就不在区间内了。但因为我们按右端点排序当前区间的右端点R_curr是大于等于之前所有区间的右端点的所以last_point之前某个区间的右端点 一定是 R_curr的。因此当last_point L时一定有L last_point R吗是的因为last_point是之前某个区间的右端点它小于等于之前所有区间的右端点自然也小于等于当前区间的右端点排序保证了R_curr是递增的。所以条件last_point L足以说明点last_point落在当前区间[L, R]内。因此我们不需要新增点。这个逻辑是正确性的核心。简单来说我们总是把点放在当前未覆盖区间中右端点最小的那个区间的右端点上。这是一个可以被严格证明的最优策略。注意这里有一个非常关键的思维转换点。初学者容易混淆“点覆盖区间”和“区间覆盖点”。我们是在数轴上选点去覆盖区间所以判断标准是“点是否在区间内”。而按右端点排序后我们放置的点上一个区间的右端点一定是小于等于当前区间右端点的所以只要这个点大于等于当前区间的左端点它就一定落在当前区间内。3. 算法实现详解与C/C语言代码实战理解了贪心策略接下来就是编码实现。这里我会分别给出C和C语言的实现版本并详细解释每一个步骤和注意事项。3.1 数据结构设计与输入处理首先我们需要存储每个区间。通常用一个结构体C语言或类C来存储区间的左右端点。C版本实现#include iostream #include vector #include algorithm using namespace std; // 定义区间结构体 struct Interval { int left; int right; // 重载小于运算符用于按右端点排序 bool operator (const Interval other) const { return right other.right; // 按右端点升序排序 } }; int main() { int n; // 区间数量 cin n; vectorInterval intervals(n); for (int i 0; i n; i) { cin intervals[i].left intervals[i].right; } // ... 后续算法逻辑 }C语言版本实现#include stdio.h #include stdlib.h // 定义区间结构体 typedef struct { int left; int right; } Interval; // 用于qsort的比较函数按右端点升序排序 int compare(const void* a, const void* b) { Interval* intervalA (Interval*)a; Interval* intervalB (Interval*)b; return intervalA-right - intervalB-right; // 升序 } int main() { int n; scanf(%d, n); Interval* intervals (Interval*)malloc(n * sizeof(Interval)); for (int i 0; i n; i) { scanf(%d %d, intervals[i].left, intervals[i].right); } // ... 后续算法逻辑 free(intervals); // 记得释放内存 return 0; }实操要点输入格式蓝桥杯系统通常是标准输入输出。题目一般会先给一个整数n然后n行每行两个整数L, R。务必按照题目要求读取。排序C中可以使用sort配合重载的运算符或自定义比较函数。C语言中使用qsort需要自己编写比较函数。排序是算法的第一步也是关键一步千万不能错。边界情况注意区间可能为负但我们的算法不关心具体数值只关心相对大小。也要注意n为0的情况虽然题目可能保证n0。3.2 贪心算法核心逻辑实现现在实现贪心算法的核心循环。我们设定一个last_point变量初始化为一个足够小的数比如-1e9或者第一个区间左端点减1然后遍历排序后的区间。C完整代码#include iostream #include vector #include algorithm using namespace std; struct Interval { int left; int right; bool operator (const Interval other) const { return right other.right; } }; int main() { int n; cin n; vectorInterval intervals(n); for (int i 0; i n; i) { cin intervals[i].left intervals[i].right; } // 1. 按区间右端点升序排序 sort(intervals.begin(), intervals.end()); // 2. 贪心算法 int count 0; // 记录选择的点数 int last_point -0x3f3f3f3f; // 初始化为一个很小的数表示上一个点的位置 for (int i 0; i n; i) { // 如果当前区间的左端点大于上一个放置的点说明需要新点覆盖 if (intervals[i].left last_point) { count; // 增加一个点 last_point intervals[i].right; // 把点放在当前区间的右端点 } // 否则last_point已经在当前区间内无需操作 } cout count endl; return 0; }C语言完整代码#include stdio.h #include stdlib.h typedef struct { int left; int right; } Interval; int compare(const void* a, const void* b) { Interval* intervalA (Interval*)a; Interval* intervalB (Interval*)b; return intervalA-right - intervalB-right; } int main() { int n; scanf(%d, n); Interval* intervals (Interval*)malloc(n * sizeof(Interval)); for (int i 0; i n; i) { scanf(%d %d, intervals[i].left, intervals[i].right); } // 排序 qsort(intervals, n, sizeof(Interval), compare); // 贪心算法 int count 0; int last_point -0x3f3f3f3f; // 使用一个足够小的整数 for (int i 0; i n; i) { if (intervals[i].left last_point) { count; last_point intervals[i].right; } } printf(%d\n, count); free(intervals); return 0; }代码逻辑解析last_point初始化初始值必须小于任何可能的区间左端点。这里用-0x3f3f3f3f一个接近负无穷的数值是竞赛编程中的常见技巧。也可以初始化为-1e9或第一个区间的left - 1。核心判断if (intervals[i].left last_point)这是算法的灵魂。如果成立意味着之前放置的所有点其实就是最近放置的那个点last_point都无法覆盖当前区间因为当前区间整个都在last_point的右边。此时我们必须新增一个点。点的放置last_point intervals[i].right我们将新点放置在当前区间的右端点。为什么是当前区间因为我们是按右端点排序的当前区间是第一个未被覆盖的区间左端点大于last_point而它的右端点是最小的可能覆盖它的点之一另一个可选点是左端点但右端点更优原因前面已论证。count计数记录我们放置的点的总数也就是最终答案。3.3 算法正确性简要证明与复杂度分析正确性证明贪心选择性质与最优子结构贪心选择性质存在一个最优解其第一个点位于所有区间中右端点最小的那个区间的右端点。证明设所有区间中右端点最小的区间为I_min其右端点为R_min。考虑任意一个最优解如果这个最优解的第一个点不在R_min而在某个位置P。如果P R_min那么P无法覆盖I_min矛盾。如果P R_min那么我们可以将第一个点移动到R_min它仍然覆盖所有原本被P覆盖的区间因为R_min更靠右并且仍然覆盖I_min。所以总可以找到一个最优解从R_min开始。最优子结构在做出了第一个点的选择放在R_min后剩下的问题是在那些左端点大于R_min的区间中继续选点。这构成了一个原问题的子问题且其最优解与全局最优解兼容。复杂度分析时间复杂度主要开销在排序上。使用快速排序Csort或 Cqsort平均时间复杂度为 O(n log n)。之后的贪心遍历是 O(n)。所以总时间复杂度为O(n log n)。空间复杂度存储n个区间需要 O(n) 的空间。排序可能使用 O(log n) 的栈空间递归。整体空间复杂度为O(n)。对于蓝桥杯系统常见的 n 在 10^5 以内的数据规模O(n log n) 的算法是完全可行的。4. 关键细节、边界条件与调试技巧即使算法思路清晰实现时也常常会遇到一些“坑”。下面是我在刷题和教学中总结的几个关键细节和调试技巧。4.1 区间端点与排序的细节处理区间是闭区间还是开区间题目“藏匿的刺客”通常描述为“在[Li, Ri]范围内”这暗示是闭区间。我们的算法if (intervals[i].left last_point)对于闭区间是完美的。如果题目说是开区间(Li, Ri)那么判断条件需要改为if (intervals[i].left last_point)因为点不能在开区间的端点上。务必仔细读题右端点相等时如何排序在我们的排序比较函数中只比较了右端点。如果两个区间右端点相同左端点不同它们的顺序会影响结果吗让我们测试一下区间[1, 5]和[3, 5]。按右端点排序顺序可以是[1,5], [3,5]或[3,5], [1,5]。顺序1:[1,5], [3,5]。last_point初始为负无穷。处理[1,5]:1 -inf新增点于5last_point5。处理[3,5]:3 5点5已覆盖不新增。结果1个点。顺序2:[3,5], [1,5]。处理[3,5]:3 -inf新增点于5last_point5。处理[1,5]:1 5点5已覆盖不新增。结果1个点。 结果一致。实际上对于右端点相同的区间无论左端点大小只要第一个区间被放置了点在右端点这个点必然能覆盖所有其他右端点相同且左端点小于等于该右端点的区间。所以按右端点单关键字排序是足够的。但为了代码清晰和避免不必要的疑虑可以在右端点相同时按左端点升序排序return a.right b.right ? a.left b.left : a.right b.right;。数据范围与溢出题目中Li和Ri可能是很大的整数比如10^9。last_point的初始值要足够小。使用-0x3f3f3f3f约 -10^9在多数情况下是安全的但如果数据范围更大可以考虑使用LONG_MINCclimits中的LLONG_MIN或-1e18。4.2 常见错误与排查清单在实现上述算法时新手容易犯以下几个错误错误现象可能原因解决方案答案总是比预期多1last_point初始化不当。例如初始化为0而所有区间左端点都大于0导致第一个区间被误判为需要新增点。将last_point初始化为一个绝对小于所有Li的值如-0x3f3f3f3f或intervals[0].left - 1排序后。答案总是比预期少判断条件写反了写成了if (intervals[i].right last_point)或其他。严格检查判断逻辑是否需要新增点的条件是当前区间是否未被上一个点覆盖即当前区间左端点 上一个点位置。排序错误导致答案错误排序函数写错了例如按左端点排序。在排序后打印前几个区间确认是按右端点升序排列的。处理大量数据时超时使用了低效的排序算法如冒泡排序 O(n^2)。确保使用 O(n log n) 的排序如sort或qsort。遇到特定测试用例失败没有考虑区间端点相等或区间包含的情况。使用多个测试用例验证包括1. 区间完全不重叠[1,2], [3,4], [5,6](答案应为3)。2. 区间完全重叠[1,5], [2,3], [3,4](答案应为1)。3. 一个区间包含另一个[1,10], [2,5](答案应为1)。4. 右端点相同[1,5], [3,5], [5,5](答案应为1)。调试技巧小数据测试不要一上来就跑大数据。先用手算几个简单例子确保程序输出与你的笔算结果一致。打印中间变量在循环中打印i,intervals[i].left,intervals[i].right,last_point,count的值观察每一步的决策是否符合预期。边界测试测试 n1, n0如果允许的情况。测试区间为负的情况。4.3 算法变种与相关题目链接“区间选点”是贪心算法的一个基础模型理解它有助于解决一系列变种问题区间分组问题给定若干区间要求将其分成尽可能少的组使得每组内的区间两两互不重叠即同一组内的任意两个区间没有交集。这实际上是求区间的“最大厚度”可以用差分数组或“活动安排”的贪心思路按左端点排序用小顶堆维护各组右端点。区间覆盖问题给定一个目标大区间[start, end]和若干小区间选择最少的小区间使得它们的并集能完全覆盖目标区间。贪心策略是在所有左端点 当前已覆盖区域右端点的区间中选择右端点最大的那个。合并区间将所有重叠的区间合并。这是很多数据处理中的常见操作。在蓝桥杯和力扣LeetCode上有很多相关题目LeetCode 452. 用最少数量的箭引爆气球几乎和“藏匿的刺客”一模一样只是背景换成了射箭戳气球。LeetCode 435. 无重叠区间给定一个区间集合需要移除最少数量的区间使得剩余区间互不重叠。可以转化为“最多能保留多少个不重叠区间”。LeetCode 56. 合并区间基础操作需要熟练掌握。LeetCode 1024. 视频拼接区间覆盖问题的典型代表。解决“藏匿的刺客”这道题相当于掌握了解决这一类问题的通用钥匙。关键在于深刻理解“按右端点排序”这一贪心策略的内在逻辑而不是死记硬背代码模板。5. 从解题到举一反三贪心算法的思维构建通过“藏匿的刺客”这道题我们可以提炼出学习和应用贪心算法的一般方法论问题建模首先将实际问题抽象成清晰的数学模型。识别出这是区间问题、调度问题、背包问题还是其他经典模型。寻找贪心策略思考“在当前步骤什么选择看起来是最优的” 常见的贪心策略有按某种规则排序如右端点、左端点、权重/长度、优先选择“最紧迫”或“效益最高”的任务、总是做出对当前最有利的局部决策。验证贪心性质这是最难也是最重要的一步。需要问自己两个问题贪心选择性质每一步的局部最优选择是否能保证构成全局最优解的一部分通常可以采用“替换法”证明假设有一个最优解我们可以用我们的贪心选择替换掉它的第一个选择而不会使解变差。最优子结构做出贪心选择后剩下的子问题是否和原问题具有相同的性质是否可以通过递归或迭代的方式同样用贪心解决实现与验证用代码实现策略并用多种测试用例尤其是边界用例进行验证。对于竞赛或面试如果无法严格证明但直觉强烈且能通过所有样例有时也可以先使用。回到我们的题目“按右端点排序每次选择当前未被覆盖的区间中右端点最小的区间的右端点”这个策略完美满足了上述两个性质。它之所以有效是因为区间的“结束时间”右端点决定了它还能“容忍”多晚被覆盖。结束得越早的区间越需要被优先考虑安排点去覆盖它。最后分享一个我自己的调试习惯对于贪心类题目我总会先写一个暴力搜索DFS的解法用于小数据范围比如n10的验证。虽然暴力解法效率极低但它能给出绝对正确的结果。用这个结果来验证我的贪心算法在小数据上的正确性能极大增强信心。当贪心算法和暴力解在所有小数据样例上都一致时再将其应用到大数据范围。这种“双保险”的调试方法在应对复杂贪心题时非常有效。 贪心算法实战：从区间覆盖问题到蓝桥杯“藏匿的刺客”题解
1. 项目概述从一道蓝桥杯真题看区间覆盖问题的实战解法最近在整理蓝桥杯的算法训练题翻到了ALGO-986 “藏匿的刺客”。这道题在各大OJ平台和蓝桥杯备考圈里讨论度不低它本质上是一个经典的“区间覆盖”问题但披上了一层有趣的故事外衣。题目大意是有若干个刺客在题目中表现为数轴上的线段区间你需要找出最少的“监视点”使得每个区间内至少有一个点被覆盖。听起来是不是有点像安排哨兵站岗或者给一系列会议安排最少会议室的问题没错这类问题在算法面试和竞赛中非常常见是贪心算法的经典应用场景。我之所以想专门聊聊这道题是因为它在理解贪心策略的“为什么”上非常有代表性。很多初学者在学贪心时总觉得“这策略看起来对但怎么证明呢”或者“为什么按左端点排序不行非得按右端点排序”。通过“藏匿的刺客”这道题我们可以把区间覆盖、区间选点这些问题的底层逻辑彻底掰开揉碎讲清楚。无论你是正在备战蓝桥杯的C/C语言选手还是单纯想巩固一下贪心算法这篇文章都会带你从问题本质出发一步步推导出最优解并分享一些我调试和优化这类代码的实战心得。2. 问题本质与数学模型抽象2.1 题目重述与核心诉求我们先抛开“刺客”这个背景把问题还原到最纯粹的数学模型。假设我们有一组区间每个区间由两个整数[Li, Ri]表示代表刺客可能藏匿的范围。我们的目标是在数轴上选择尽可能少的点使得每一个区间内都至少包含一个我们选择的点。举个例子假设区间是[1, 3],[2, 5],[3, 6]。如果我们把点选在位置3那么它同时落在了三个区间内我们只需要1个点就满足了所有区间。如果区间是[1, 2]和[3, 4]由于它们没有重叠我们至少需要2个点比如在1.5和3.5各放一个。所以问题的核心诉求非常明确最小化点的数量实现对所有区间的覆盖。在算法领域这被称为“区间选点问题”或“最小点覆盖问题”。2.2 贪心策略的直觉与严谨思考为什么这个问题可以用贪心算法解决贪心算法的核心是“每一步都做出当前看来最优的选择”并希望这样的局部最优能导致全局最优。对于区间覆盖一个很自然的想法是“既然要覆盖所有区间那我应该优先把点放在能覆盖最多区间的位置。” 这个位置往往就是多个区间重叠最深的地方。如何找到这个“重叠最深”的地方呢有两种常见的排序思路按区间左端点升序排序直觉上我们从左到右处理区间尽量把点往右放让它能覆盖后面更多的区间。但这里有个陷阱如果第一个区间很长覆盖了后面很多区间但把点放在它很靠右的位置可能会错过一些结束很早的区间。按区间右端点升序排序这是被证明正确的策略。其思想是为了覆盖一个区间点放在这个区间内的任何位置都可以。但为了让它有潜力覆盖后续更多的区间我们应该把它放在尽可能靠右的位置不对恰恰相反应该放在尽可能靠左的、但仍能覆盖当前区间的位置也就是当前区间的右端点。因为右端点是这个区间能“够到”的最远位置如果连当前区间的右端点都无法覆盖某个后续区间那么放在当前区间内更靠左的位置也同样无法覆盖。反之把点放在当前区间的右端点为当前区间提供了覆盖同时这个点因为位置相对靠右相对于本区间它更有可能也落在后面那些右端点更靠后的区间里。让我们严谨地推演一下按右端点排序的贪心策略将所有区间按照右端点从小到大进行排序。初始化一个变量last_point记录上一个放置的点的位置。初始化为一个非常小的数比如负无穷。从左到右遍历排序后的区间。对于当前区间[L, R]如果last_point小于L说明上一个放置的点无法覆盖当前区间因为当前区间的左端点都在上一个点的右边。那么我们必须在当前区间内新放置一个点。为了最大化这个点的效用我们把它放在当前区间的右端点R。然后更新last_point R。如果last_point大于等于L说明上一个放置的点已经落在当前区间内因为当前区间左端点Llast_point 当前区间右端点R这里需要确认last_point是上一个区间的右端点它可能大于当前区间的右端点吗排序后当前区间的右端点R_curr是大于等于上一个区间的右端点last_point的。所以条件last_point L成立时last_point一定小于等于R_curr吗不一定last_point是上一个区间的右端点它可能大于当前区间的右端点。例如区间[1, 10]和[2, 3]按右端点排序后是[2, 3],[1, 10]。处理第一个区间后last_point3。处理第二个区间[1, 10]时L1因为3 1我们认为点3已经覆盖了区间[1,10]这显然是正确的。所以判断条件应该是last_point L才需要新增点。如果last_point L无论last_point是否大于R点last_point都已经在区间[L, R]内了吗不对如果last_point R点就不在区间内了。但因为我们按右端点排序当前区间的右端点R_curr是大于等于之前所有区间的右端点的所以last_point之前某个区间的右端点 一定是 R_curr的。因此当last_point L时一定有L last_point R吗是的因为last_point是之前某个区间的右端点它小于等于之前所有区间的右端点自然也小于等于当前区间的右端点排序保证了R_curr是递增的。所以条件last_point L足以说明点last_point落在当前区间[L, R]内。因此我们不需要新增点。这个逻辑是正确性的核心。简单来说我们总是把点放在当前未覆盖区间中右端点最小的那个区间的右端点上。这是一个可以被严格证明的最优策略。注意这里有一个非常关键的思维转换点。初学者容易混淆“点覆盖区间”和“区间覆盖点”。我们是在数轴上选点去覆盖区间所以判断标准是“点是否在区间内”。而按右端点排序后我们放置的点上一个区间的右端点一定是小于等于当前区间右端点的所以只要这个点大于等于当前区间的左端点它就一定落在当前区间内。3. 算法实现详解与C/C语言代码实战理解了贪心策略接下来就是编码实现。这里我会分别给出C和C语言的实现版本并详细解释每一个步骤和注意事项。3.1 数据结构设计与输入处理首先我们需要存储每个区间。通常用一个结构体C语言或类C来存储区间的左右端点。C版本实现#include iostream #include vector #include algorithm using namespace std; // 定义区间结构体 struct Interval { int left; int right; // 重载小于运算符用于按右端点排序 bool operator (const Interval other) const { return right other.right; // 按右端点升序排序 } }; int main() { int n; // 区间数量 cin n; vectorInterval intervals(n); for (int i 0; i n; i) { cin intervals[i].left intervals[i].right; } // ... 后续算法逻辑 }C语言版本实现#include stdio.h #include stdlib.h // 定义区间结构体 typedef struct { int left; int right; } Interval; // 用于qsort的比较函数按右端点升序排序 int compare(const void* a, const void* b) { Interval* intervalA (Interval*)a; Interval* intervalB (Interval*)b; return intervalA-right - intervalB-right; // 升序 } int main() { int n; scanf(%d, n); Interval* intervals (Interval*)malloc(n * sizeof(Interval)); for (int i 0; i n; i) { scanf(%d %d, intervals[i].left, intervals[i].right); } // ... 后续算法逻辑 free(intervals); // 记得释放内存 return 0; }实操要点输入格式蓝桥杯系统通常是标准输入输出。题目一般会先给一个整数n然后n行每行两个整数L, R。务必按照题目要求读取。排序C中可以使用sort配合重载的运算符或自定义比较函数。C语言中使用qsort需要自己编写比较函数。排序是算法的第一步也是关键一步千万不能错。边界情况注意区间可能为负但我们的算法不关心具体数值只关心相对大小。也要注意n为0的情况虽然题目可能保证n0。3.2 贪心算法核心逻辑实现现在实现贪心算法的核心循环。我们设定一个last_point变量初始化为一个足够小的数比如-1e9或者第一个区间左端点减1然后遍历排序后的区间。C完整代码#include iostream #include vector #include algorithm using namespace std; struct Interval { int left; int right; bool operator (const Interval other) const { return right other.right; } }; int main() { int n; cin n; vectorInterval intervals(n); for (int i 0; i n; i) { cin intervals[i].left intervals[i].right; } // 1. 按区间右端点升序排序 sort(intervals.begin(), intervals.end()); // 2. 贪心算法 int count 0; // 记录选择的点数 int last_point -0x3f3f3f3f; // 初始化为一个很小的数表示上一个点的位置 for (int i 0; i n; i) { // 如果当前区间的左端点大于上一个放置的点说明需要新点覆盖 if (intervals[i].left last_point) { count; // 增加一个点 last_point intervals[i].right; // 把点放在当前区间的右端点 } // 否则last_point已经在当前区间内无需操作 } cout count endl; return 0; }C语言完整代码#include stdio.h #include stdlib.h typedef struct { int left; int right; } Interval; int compare(const void* a, const void* b) { Interval* intervalA (Interval*)a; Interval* intervalB (Interval*)b; return intervalA-right - intervalB-right; } int main() { int n; scanf(%d, n); Interval* intervals (Interval*)malloc(n * sizeof(Interval)); for (int i 0; i n; i) { scanf(%d %d, intervals[i].left, intervals[i].right); } // 排序 qsort(intervals, n, sizeof(Interval), compare); // 贪心算法 int count 0; int last_point -0x3f3f3f3f; // 使用一个足够小的整数 for (int i 0; i n; i) { if (intervals[i].left last_point) { count; last_point intervals[i].right; } } printf(%d\n, count); free(intervals); return 0; }代码逻辑解析last_point初始化初始值必须小于任何可能的区间左端点。这里用-0x3f3f3f3f一个接近负无穷的数值是竞赛编程中的常见技巧。也可以初始化为-1e9或第一个区间的left - 1。核心判断if (intervals[i].left last_point)这是算法的灵魂。如果成立意味着之前放置的所有点其实就是最近放置的那个点last_point都无法覆盖当前区间因为当前区间整个都在last_point的右边。此时我们必须新增一个点。点的放置last_point intervals[i].right我们将新点放置在当前区间的右端点。为什么是当前区间因为我们是按右端点排序的当前区间是第一个未被覆盖的区间左端点大于last_point而它的右端点是最小的可能覆盖它的点之一另一个可选点是左端点但右端点更优原因前面已论证。count计数记录我们放置的点的总数也就是最终答案。3.3 算法正确性简要证明与复杂度分析正确性证明贪心选择性质与最优子结构贪心选择性质存在一个最优解其第一个点位于所有区间中右端点最小的那个区间的右端点。证明设所有区间中右端点最小的区间为I_min其右端点为R_min。考虑任意一个最优解如果这个最优解的第一个点不在R_min而在某个位置P。如果P R_min那么P无法覆盖I_min矛盾。如果P R_min那么我们可以将第一个点移动到R_min它仍然覆盖所有原本被P覆盖的区间因为R_min更靠右并且仍然覆盖I_min。所以总可以找到一个最优解从R_min开始。最优子结构在做出了第一个点的选择放在R_min后剩下的问题是在那些左端点大于R_min的区间中继续选点。这构成了一个原问题的子问题且其最优解与全局最优解兼容。复杂度分析时间复杂度主要开销在排序上。使用快速排序Csort或 Cqsort平均时间复杂度为 O(n log n)。之后的贪心遍历是 O(n)。所以总时间复杂度为O(n log n)。空间复杂度存储n个区间需要 O(n) 的空间。排序可能使用 O(log n) 的栈空间递归。整体空间复杂度为O(n)。对于蓝桥杯系统常见的 n 在 10^5 以内的数据规模O(n log n) 的算法是完全可行的。4. 关键细节、边界条件与调试技巧即使算法思路清晰实现时也常常会遇到一些“坑”。下面是我在刷题和教学中总结的几个关键细节和调试技巧。4.1 区间端点与排序的细节处理区间是闭区间还是开区间题目“藏匿的刺客”通常描述为“在[Li, Ri]范围内”这暗示是闭区间。我们的算法if (intervals[i].left last_point)对于闭区间是完美的。如果题目说是开区间(Li, Ri)那么判断条件需要改为if (intervals[i].left last_point)因为点不能在开区间的端点上。务必仔细读题右端点相等时如何排序在我们的排序比较函数中只比较了右端点。如果两个区间右端点相同左端点不同它们的顺序会影响结果吗让我们测试一下区间[1, 5]和[3, 5]。按右端点排序顺序可以是[1,5], [3,5]或[3,5], [1,5]。顺序1:[1,5], [3,5]。last_point初始为负无穷。处理[1,5]:1 -inf新增点于5last_point5。处理[3,5]:3 5点5已覆盖不新增。结果1个点。顺序2:[3,5], [1,5]。处理[3,5]:3 -inf新增点于5last_point5。处理[1,5]:1 5点5已覆盖不新增。结果1个点。 结果一致。实际上对于右端点相同的区间无论左端点大小只要第一个区间被放置了点在右端点这个点必然能覆盖所有其他右端点相同且左端点小于等于该右端点的区间。所以按右端点单关键字排序是足够的。但为了代码清晰和避免不必要的疑虑可以在右端点相同时按左端点升序排序return a.right b.right ? a.left b.left : a.right b.right;。数据范围与溢出题目中Li和Ri可能是很大的整数比如10^9。last_point的初始值要足够小。使用-0x3f3f3f3f约 -10^9在多数情况下是安全的但如果数据范围更大可以考虑使用LONG_MINCclimits中的LLONG_MIN或-1e18。4.2 常见错误与排查清单在实现上述算法时新手容易犯以下几个错误错误现象可能原因解决方案答案总是比预期多1last_point初始化不当。例如初始化为0而所有区间左端点都大于0导致第一个区间被误判为需要新增点。将last_point初始化为一个绝对小于所有Li的值如-0x3f3f3f3f或intervals[0].left - 1排序后。答案总是比预期少判断条件写反了写成了if (intervals[i].right last_point)或其他。严格检查判断逻辑是否需要新增点的条件是当前区间是否未被上一个点覆盖即当前区间左端点 上一个点位置。排序错误导致答案错误排序函数写错了例如按左端点排序。在排序后打印前几个区间确认是按右端点升序排列的。处理大量数据时超时使用了低效的排序算法如冒泡排序 O(n^2)。确保使用 O(n log n) 的排序如sort或qsort。遇到特定测试用例失败没有考虑区间端点相等或区间包含的情况。使用多个测试用例验证包括1. 区间完全不重叠[1,2], [3,4], [5,6](答案应为3)。2. 区间完全重叠[1,5], [2,3], [3,4](答案应为1)。3. 一个区间包含另一个[1,10], [2,5](答案应为1)。4. 右端点相同[1,5], [3,5], [5,5](答案应为1)。调试技巧小数据测试不要一上来就跑大数据。先用手算几个简单例子确保程序输出与你的笔算结果一致。打印中间变量在循环中打印i,intervals[i].left,intervals[i].right,last_point,count的值观察每一步的决策是否符合预期。边界测试测试 n1, n0如果允许的情况。测试区间为负的情况。4.3 算法变种与相关题目链接“区间选点”是贪心算法的一个基础模型理解它有助于解决一系列变种问题区间分组问题给定若干区间要求将其分成尽可能少的组使得每组内的区间两两互不重叠即同一组内的任意两个区间没有交集。这实际上是求区间的“最大厚度”可以用差分数组或“活动安排”的贪心思路按左端点排序用小顶堆维护各组右端点。区间覆盖问题给定一个目标大区间[start, end]和若干小区间选择最少的小区间使得它们的并集能完全覆盖目标区间。贪心策略是在所有左端点 当前已覆盖区域右端点的区间中选择右端点最大的那个。合并区间将所有重叠的区间合并。这是很多数据处理中的常见操作。在蓝桥杯和力扣LeetCode上有很多相关题目LeetCode 452. 用最少数量的箭引爆气球几乎和“藏匿的刺客”一模一样只是背景换成了射箭戳气球。LeetCode 435. 无重叠区间给定一个区间集合需要移除最少数量的区间使得剩余区间互不重叠。可以转化为“最多能保留多少个不重叠区间”。LeetCode 56. 合并区间基础操作需要熟练掌握。LeetCode 1024. 视频拼接区间覆盖问题的典型代表。解决“藏匿的刺客”这道题相当于掌握了解决这一类问题的通用钥匙。关键在于深刻理解“按右端点排序”这一贪心策略的内在逻辑而不是死记硬背代码模板。5. 从解题到举一反三贪心算法的思维构建通过“藏匿的刺客”这道题我们可以提炼出学习和应用贪心算法的一般方法论问题建模首先将实际问题抽象成清晰的数学模型。识别出这是区间问题、调度问题、背包问题还是其他经典模型。寻找贪心策略思考“在当前步骤什么选择看起来是最优的” 常见的贪心策略有按某种规则排序如右端点、左端点、权重/长度、优先选择“最紧迫”或“效益最高”的任务、总是做出对当前最有利的局部决策。验证贪心性质这是最难也是最重要的一步。需要问自己两个问题贪心选择性质每一步的局部最优选择是否能保证构成全局最优解的一部分通常可以采用“替换法”证明假设有一个最优解我们可以用我们的贪心选择替换掉它的第一个选择而不会使解变差。最优子结构做出贪心选择后剩下的子问题是否和原问题具有相同的性质是否可以通过递归或迭代的方式同样用贪心解决实现与验证用代码实现策略并用多种测试用例尤其是边界用例进行验证。对于竞赛或面试如果无法严格证明但直觉强烈且能通过所有样例有时也可以先使用。回到我们的题目“按右端点排序每次选择当前未被覆盖的区间中右端点最小的区间的右端点”这个策略完美满足了上述两个性质。它之所以有效是因为区间的“结束时间”右端点决定了它还能“容忍”多晚被覆盖。结束得越早的区间越需要被优先考虑安排点去覆盖它。最后分享一个我自己的调试习惯对于贪心类题目我总会先写一个暴力搜索DFS的解法用于小数据范围比如n10的验证。虽然暴力解法效率极低但它能给出绝对正确的结果。用这个结果来验证我的贪心算法在小数据上的正确性能极大增强信心。当贪心算法和暴力解在所有小数据样例上都一致时再将其应用到大数据范围。这种“双保险”的调试方法在应对复杂贪心题时非常有效。