贪心算法经典题型：导弹打飞机的冷却调度与资源复用

1. 先把“导弹打飞机”这道题说清楚1.1 题面到底在问什么“导弹打飞机”这个题目名字一听就很带感实际上它不是军事模拟而是算法竞赛里一道非常经典的贪心题地位大概相当于贪心专题的“入门必刷”之一。题面通常长这样有一批敌机每架飞机有一个到达时间并且只会停留一段时间你必须在这个时间窗口内发射导弹把它打下来。每发射一枚导弹这个导弹就会进入冷却状态需要过一段时间才能再次发射。问你最少需要准备多少枚导弹才能保证把所有飞机都拦住。先别急着觉得“这不就是安排导弹嘛”其实把条件再翻译一下就是另一回事了每架飞机是一个带开始时间和结束时间的时间窗口每枚导弹是一个可以被反复使用的资源每次使用之后要冷却一段时间才能复用。问题变成在保证每个窗口都能被覆盖的前提下最少需要几个可复用资源。这就和“最少需要几个会议主持人才能cover所有预约”、“最少几条生产线才能跑完所有带窗口的任务”本质一样了属于典型的区间调度变体。这篇东西适合谁看如果你正在刷算法、准备机试或面试尤其是贪心章节还没完全建立起感觉的同学这道题是一个很好的“练贪心直觉”的素材。它的代码量不大核心就一个排序加一个数据结构维护但背后的资源复用逻辑很典型值得一气呵成吃透。1.2 为什么一看到这道题就该往贪心方向想很多人看到这类题第一反应是搜索枚举每架飞机用哪枚导弹打。但稍微估一下复杂度就知道不现实假设飞机有50架那状态空间基本是天文数字而且飞机数量稍微上来一点搜索连跑都跑不动。DP倒是可以考虑但状态维度要高得多你需要记录每枚导弹的冷却剩余时间这个状态根本无法压缩。而贪心的合理性恰恰来自问题的结构。飞机有明确的到达顺序导弹的冷却时间是一个确定值每一次决策只影响“当前这架飞机由谁来打”而且选择导弹的策略非常直观谁“够得着”就用谁但用哪一枚有讲究。只要有局部最优决策可以卡住全局最优贪心就是最合适的方向。实际上这类“资源复用 时间窗口”的题十有八九就是排序 贪心选边核心就一句话当前任务来了看看现有的空闲资源里有没有能接得住的有就挑最合适的一个用没有才新开一个资源。这个思路再往下挖一下就是“每次尽量用掉那个最不灵活的资源”保留下更灵活的资源应对后续的不确定性。这句话是整个算法的灵魂后面我会重点讲。1.3 从题目到数学模型的翻译过程写代码之前先要建立一个干净的数学模型。假设有N批飞机第i批飞机的到达时间是a[i]它停留在空中的时间窗口是[a[i], b[i]]也就是说你可以在a[i]到b[i]之间的任意时刻发射导弹打它但超过b[i]它就飞走了打不到。发射导弹需要一枚导弹进入一次发射流程发射结束后这枚导弹需要冷却C秒才能再次发射。问最少需要准备多少枚导弹。这里为了表述方便我在实际代码里把“导弹下一次可用的时间”作为唯一需要维护的状态记为next_free_time。一架飞机能被某枚导弹拦截必须满足next_free_time a[i]并且拦截后这枚导弹的next_free_time变成a[i] C因为打完这一发之后它最早也得等到a[i]C才能接下一单。为什么用a[i]作为发射时刻而不是b[i]因为越早打越能早进入冷却对后续任务越有利这是显然的所以最优解里每架飞机一定是到达后立刻打不拖到窗口末尾。于是整个问题就压缩成了维护若干枚导弹的next_free_time每来一架新飞机在已有的导弹里找一枚满足条件的最合适导弹来用没有合适的就新开一枚。这个模型是所有后续分析和代码实现的地基整个贪心策略也都是围绕它展开的。2. 贪心策略别急着把导弹全部打出去2.1 排序是第一件事但不是唯一的事通用的第一步是按到达时间a[i]升序处理飞机。为什么要排序因为在时间轴上处理任务只有先处理先到达的才能保证后续决策时“当前时间”这个概念是单调递增的。如果你不排序先处理了一架很晚到达的飞机那它会把一些导弹的冷却时间更新得很靠后然后你再处理早到的飞机发现没有导弹可用就错误地多开了一枚这种错乱会让结果完全失真。排序之后核心就是维护一个集合。集合里装的是所有“已经拥有过”的导弹的next_free_time。注意这个集合不是只装空闲的导弹而是所有导弹当前状态都体现在这个时间点上。每次来一架飞机时我先在这个集合里找有没有满足next_free_time a[i]的导弹。如果有说明这枚导弹已经冷却完毕可以复用如果没有说明现役导弹全部还在冷却那只能新造一枚。这里马上会出现一个新手最容易翻车的岔路口如果集合里有多枚导弹都满足条件用哪一枚很多人会觉得既然都能用随便选一个不就行了甚至觉得应该选最早冷却好的那枚。但这两个直觉一个是碰运气一个是错的真正的选择应该是后面要说的“选最晚冷却完的那枚”。2.2 为什么是用“最晚可用”而不是“最早可用”这个点值得掰开揉碎讲因为它才是这道题里贪心策略的核心。假设现在有两枚导弹下一枚可用的时刻分别是t1 5和t2 9当前飞机的到达时间是10也就是说两枚在当前时刻都冷却完了都能打。如果你选了最早可用t1 5那枚去打打完它下一次可用变成10 C留下t2 9那枚。如果接下来马上又飞来一架飞机到达时间是10 C - 1也就是刚好卡在这枚导弹还没冷却好的时刻那你只留下了一枚9可用的导弹够不够用得看运气。但如果你反着选用了t2 9这枚留下t1 5那枚那下一架飞机来了哪怕到达时间更早只要不早于5那枚t1也不可能已经冷却完于是你有更大的余地应付那种“突然早到”的任务。更直白一点说冷却结束时间越早的导弹越是一个“随时能顶上”的灵活资源冷却结束时间越晚但已经可用的导弹反而更接近“即将失去可用性”的状态。当面前所有选择都能完成任务时你应该优先用掉那个“最不灵活的”把最灵活的留在手里。这就跟你手里有100块钱和50块钱两张钞票买一样东西时优先花掉那张更可能被找不开的大钞一个道理。这个策略在数学上叫延迟选择也叫最紧资源优先。很多经典贪心都能归到这个框架里比如换零钱问题有时也用类似思路但在这里套得最自然。2.3 正确性怎么直观理解有的读者看到这里可能会想你说用最晚可用一定对但怎么证明其实这道题的贪心正确性可以用交换论证来顺一遍。假设在某一步贪心选择了最晚可用的导弹X时间为t2而某个最优解里选择的是更早可用的导弹Y时间为t1t1 t2并且最优解里X在后续某一刻被用来打另一架飞机或者一直闲置。现在把两者的角色交换让Y去执行X原本要执行的后续任务让X去完成当前这架飞机。由于Y的冷却结束时间t1比X的t2更早Y对后续任务来说只会更从容不会更紧张所以交换之后不会破坏任何约束。于是一个最优解可以被调整成跟贪心选择一致而不变差。反复做这个交换就能说明贪心的每一步都有某个最优解在配合它最终贪心得到的答案就是全局最优。听上去有点绕但画个时间轴就清楚了。这个证明不用背理解“把更灵活的资源留下”即可。应付笔试面试时你能把这个直觉讲明白面试官一般就会放过你。3. 代码实现从想法到能提交的完整方案3.1 C实现multiset是天然帮手维护“一堆导弹的可用时间”这个集合C里最顺手的工具是multiset。为什么不用priority_queue因为我们需要查找“小于等于当前到达时间的最大值”也就是lower_bound或者upper_bound的边界操作multiset是平衡树支持这些操作而priority_queue只能取堆顶不能灵活寻找某个阈值附近的元素。核心代码如下我把注释写在关键位置#include bits/stdc.h using namespace std; struct Plane { int start, end; }; int main() { int n, cool; cin n cool; vectorPlane planes(n); for (int i 0; i n; i) cin planes[i].start planes[i].end; // 必须按到达时间排序这是所有时间线处理的基础 sort(planes.begin(), planes.end(), [](const Plane a, const Plane b) { return a.start b.start; }); multisetint freeTimes; // 存储所有现存导弹的下次可用时间 int ans 0; // 新开导弹的数量 for (auto p : planes) { // 条件判断现役导弹里是否存在 next_free_time p.start auto it freeTimes.upper_bound(p.start); if (it freeTimes.begin()) { // 没有可用的现役导弹新开一枚 ans; freeTimes.insert(p.start cool); } else { // 存在可用导弹优先用“最晚冷却完成但仍满足条件的” --it; freeTimes.erase(it); freeTimes.insert(p.start cool); } } cout ans endl; return 0; }这段代码里最关键的一点是upper_bound(p.start)的返回值它指向第一个大于p.start的元素那么这个元素之前一个也就是--it指向的就是最后一个小于等于p.start的元素也就是“最晚可用导弹”。如果upper_bound返回了begin()说明第一个元素都大于p.start换句话说没有任何一枚导弹冷却结束时间小于等于当前到达时间全都不满足复用条件新开即可。有人会问这里要不要判断飞机窗口结束时间p.end和发射开始时间的关系实际上如果我们选择在p.start时刻立刻发射并且发射本身不耗时那只要p.start p.end就一定合法。所以窗口的右端在这个基础模型里其实用不到它只会在变体里起作用这点后面再说。3.2 Python实现用sortedcontainers或有序列表模拟Python标准库里没有内置平衡树手写一个红黑树显然划不来。最简单稳妥的办法是用数组维护一个有序列表配合bisect库操作虽然最坏情况插入是O(n)但在很多OJ数据量没那么疯的场景下完全能跑。import bisect def min_missiles(planes, cool): planes.sort(keylambda x: x[0]) free_times [] ans 0 for start, end in planes: idx bisect.bisect_right(free_times, start) - 1 if idx 0: ans 1 bisect.insort(free_times, start cool) else: free_times.pop(idx) bisect.insort(free_times, start cool) return ans原理和C完全一致bisect_right找到第一个大于start的位置减一就是最后一个小于等于start的位置。如果这个位置是-1说明没有可用导弹。这里的小技巧是用bisect.insort保持列表有序而不是每次sort一遍不然复杂度会退化得很厉害。如果你用的环境支持也可以装sortedcontainers库里的SortedList它内部是跳表实现插入删除都是O(log n)写起来和multiset差不多。但在机试现场大概率不让装第三方库所以我个人更推荐bisect方案足够稳。3.3 几个容易错的小地方第一冷却时间的数据类型。飞机的到达时间可能是10^9级别加上冷却时间很可能超出int范围建议直接用long long不然样例能过大数据直接WA。这不是危言耸听我见过很多人在这上面栽过。第二multiset的erase方法。如果你写freeTimes.erase(it)那是删除指定迭代器指向的一个元素没问题。但如果你写freeTimes.erase(it)那会删除所有值等于it的元素如果有多枚导弹冷却结束时间恰好相同就会一下子全被删光后面的逻辑直接乱了。这是一个经典陷阱。第三边界情况飞机窗口的右端点刚好等于左端点也就是只有一瞬间可以拦截或者冷却时间为0。冷却时间为0意味着打完立刻能再打永远只需要一枚导弹。这个用例往往不会被特别构造但算法题里什么都可能出现处理不好就会卡在角落用例。第四如果你的题目要求输出“能拦截到的最多飞机数量”那要区分问题模型那可能是另一个动态规划问题和贪心的最小导弹数不一样。读题时一定要先确认到底是“最少导弹数”还是“最多拦截数”一字之差解法天差地别。4. 常见问题与实测排查4.1 样例能过提交死活WA问题出在哪这类题最容易出现“本地能跑通但提交不过”的情况。我先列一下最常见的几个原因方便你自查。一个是排序时按什么排。如果题目给的飞机数据不是按到达时间排好序的而你忘了排序或者sort的时候比较函数写反了那后面所有逻辑都会错这种错法通常不是WA而是答案乱来比较容易发现。比较隐蔽的是如果你按结束时间排序而不是到达时间可能出现当前处理的飞机到达时间比上一架早这会让整个“冷却结束时间”逻辑失真结果错了还很难看出来。另一个常见问题是忽略了“立即发射”的最优性。我之前说过飞机一到就应该打不要拖延。但这不是直觉就能看出来的需要想明白拖延发射只会让这枚导弹的冷却结束时间往后推对后续没有任何好处。如果你在代码里把p.start cool写成了p.end cool或者用了一个随机选的发射时间那就会引入不必要的浪费导致答案偏大。自查时盯着发射时间这个变量看就行。再有一个隐蔽的坑冷却结束时间恰好等于p.start时算不算可用按我们模型当然可用因为飞机到达的瞬间导弹也冷却完毕两者在同一时刻不冲突。所以需要找的是小于等于而不是严格小于。我代码里用的是upper_bound再往前挪一位天然包含等于的情况如果你写的是lower_bound就有可能会漏掉这个相等边界的可用导弹导致多开一枚。这是WA的重灾区。4.2 和“区间调度”对比能发现什么做过经典区间调度的人可能会疑惑那个著名的“最多能安排多少个活动”问题时策略是选结束时间最早的为什么这里变成了选冷却结束时间最晚的两个贪心方向不是矛盾了吗其实不矛盾因为它们两个是最小化目标和最大化目标的关系。活动安排问题里资源是由一个主持人代表任务不能重叠目标是在固定时间内塞进尽可能多的任务所以每个任务应该尽早结束给后面腾位置。而在导弹问题里目标是至少需要多少资源任务一个都不能少那么当任务被确定要处理时我们需要考虑的是怎么把任务分配给现有的资源让现有资源尽可能少地发生“再新开一个”的事件。用更直白的话说活动安排是“怎么安排才能让一个主持人干完最多事”导弹问题是“这些事全都要干最少找几个人来干”。前者是往一个瓶子里塞最多东西后者是给固定的一堆东西找最少容器。策略自然一左一右。理解了这层区别你对贪心的理解就会更上一个台阶就不会再因为“两个题长得像但贪心方向相反”而脑壳疼了。4.3 特殊情况与对拍验证我强烈建议你写完代码后自己写一个暴力验证器来对拍。暴力方法很简单DFS枚举每架飞机由哪枚导弹打同时维护导弹冷却状态记录最少需要的导弹数。数据小的时候比如n 8冷却时间和小范围随机跑几千组对比暴力答案和贪心答案如果不一致说明你的贪心逻辑有漏洞或者实现有bug。我实际对拍时经常发现很多不是算法的问题而是STL用错了。比如前面提到的erase误删多个元素还有迭代器失效问题。multiset在erase之后当前迭代器已经失效绝对不能再用但你可以返回下一个迭代器或者直接重新查找。很多人把erase和insert写在一起时会顺手保留一个失效迭代器下一轮循环boom。这个坑我在调试时盯了半小时才定位到。还有一个特殊情况是多批飞机共享同一个到达时间。这个场景下先处理哪一批其实无所谓因为窗口区间相同先后顺序不影响冷却结束时间的产生只要排序时比较函数保持一致答案就是稳定的。但如果你的sort用了非严格弱序比如到达时间相同时比较函数返回false又返回true那后果是未定义的可能会直接崩掉或得到随机答案。5. 变体扩展这个模型还能用到哪5.1 如果发射导弹本身需要时间现实中导弹打出去要飞一段时间才能命中不是按一下按钮就瞬间爆炸。有的变体里飞机窗口是[a[i], b[i]]导弹需要在窗口内开始发射并且经过飞行时间fly之后命中的时刻必须在b[i]之前。这时代码就比基础版多一重判断不仅要求next_free_time a[i]还要求a[i] fly b[i]而且拦截后导弹的next_free_time要更新成a[i] fly cool因为发射完了之后导弹还有冷却。这个改动并不复杂只是把“发射时刻”和“命中时刻”分开了。如果你在代码里只维护一个冷却结束时间很容易忘记飞行时间对b[i]上限的约束导致明明打不完的飞机也被算成打得完答案就不对了。遇到这种变体时我的习惯是先画一个时间轴发射时刻、命中时刻、冷却完成时刻三个点标清楚再写代码就不容易乱。5.2 如果飞机有优先级不能全拦住怎么办有些升级版问题里飞机有不同价值导弹数量有限你不能全打只能选择性地拦目标是让被击落的飞机总价值最大。这个就不再是贪心能解决的问题了因为局部最优可能牺牲了高价值目标。此时通常要用到动态规划或者费用流。但有意思的是即便目标和约束变了你之前积累的“按到达时间排序、维护冷却结束时间”这个分析框架依然有参考价值。先用这套方法判断一下哪些飞机必然无法被拦截把必死目标剔除剩下的子问题规模会小很多再去套DP就有戏。很多复杂题的解题过程就是从简单模型的思路上长出来的。5.3 其他领域里的同类模型这个模型往工程和生活里套能套出很多场景。比如客服排班一批客户来电各有等待上限客服每次接待完一位客户需要休息再比如视频编辑一大批剪辑任务各有期望完成窗口每台工作站渲染一个任务后需要清理时间甚至外卖骑手送单订单有预计取餐时间和送达限制骑手送完一单需要回到商圈才能接下一单。每次遇到这类问题只要抽掉表面名词剩下的都是一个带冷却时间的资源复用模型。我个人的建议是不要满足于把这道题AC掉而是把“贪心选择最不灵活资源”这个思维模式记下来以后遇到任何“有复用资源、有窗口任务”的调度题你都先往这个方向想。实践下来这一道题的价值远超过它本身的难度。说回我自己的做题体会第一次做这个题时我也选过最早冷却好的导弹然后对着错误的答案迷茫了很久后来画了十几个例子的时间轴才真正相信应该反着选。那之后我对贪心的理解就打通了一大块面试里被问到“为什么要用这个策略”时也再没虚过。如果你也在练贪心建议不要只背代码亲手画几组例子验证一下这个选择逻辑你会比那些只刷题的人多一层底。