★ FEATURED ARTICLE “飞机降落问题”是很多OJ上的一道经典搜索题也是面试里常被拿来考回溯基本功的题目。我自己当年第一次做它状态和现在很多卡住的同学一模一样样例通通能过直觉上也觉得思路没问题结果一提交几十个测试点里就过了两项剩下的全是WA或TLE那感觉确实挺打击人的。后来我把错误代码一行行拆开才发现根本不是“算法不会”的问题而是几个特别隐蔽的细节在作怪。这篇就把我完整的修正过程、错误原因和最终代码写出来如果你也卡在这道题上可以按下面的思路逐条对照检查。先说结论这道题本质上是一个“带时间窗口的单机调度判定问题”不能用简单的贪心排序一刀切最常见的正确做法是DFS回溯枚举所有可能的降落顺序。而很多人只过两项案例大概率踩了三个坑一是把“跑道当前可用时间”和“飞机自身到达时间”混为一谈二是回溯时没有正确恢复状态三是对时间窗口的左右边界理解有偏差。下面我按从思路到实现、再到调错的顺序把整个过程完整展开。1. 先弄清楚题目到底在考什么1.1 题面复述与数据范围先用自己的话把题目说清楚有N架飞机需要降落在同一条跑道上每架飞机都有三个参数分别是到达时间T、最大等待时间D、降落所需时间L。这架飞机可以安全降落的“开始时间窗口”就是[T, TD]也就是说它最早可以在T时刻开始降落最晚不能晚于TD时刻开始降落一旦开始降落跑道要被占用L这么久。你需要判断是否存在一种降落顺序使得所有飞机都能在各自的窗口内开始降落。能全部安排就输出YES否则输出NO。题目给的N通常不会很大一般在10到15这个量级个别版本可能会到18左右。这个数据范围本身就是关键词它几乎是在明示出题人想要的解法搜索。因为全排列的时间复杂度是O(n!)当n10时是360万次n12时大约4.79亿次如果不做任何优化确实会超时但只要加一点剪枝或启发式排序跑完是没问题的。反过来如果n给到了100以上那才需要考虑贪心或DP之类的算法。可这道题N这么小反而说明DFS这个方向大概率是对的。1.2 为什么不能无脑排序贪心很多人的第一反应是既然要求一个顺序那我把飞机按某个关键字排个序然后从头到尾扫一遍如果过程中发现某架飞机窗口过了就输出NO否则YES。我自己一开始也是这么干的按最晚开始时间从小到大排代码非常短样例也过了结果提交之后只过了两个点直接被判WA。问题出在哪这种区间调度贪心只有在“处理时间相同”或者“窗口互不重叠”的特定条件下才成立。这里的飞机降落耗时L是完全不同的有的飞机耗时长有的飞机耗时短。你按最晚开始时间排序等于默认了“紧急的先降落”就一定最优。但事实上某架飞机虽然紧急如果它耗时特别长先安排它反而会把跑道占住导致后面好几架虽然窗口还宽裕、但来不及降落的飞机全部晚点。我举个例子说明贪心为什么会失败。假设有三架飞机飞机A窗口[T0, TD10]耗时6飞机B窗口[T0, TD1]耗时1飞机C窗口[T2, TD3]耗时1如果按最晚开始时间排序B最紧急所以先排B没问题B在0到1降落。接着C窗口是[2,3]跑道1时刻空闲C可以在2到3降落。最后A在3到9降落窗口是[0,10]完全合法这样贪心恰好成功。那换一组飞机A窗口[T0, TD10]耗时9飞机B窗口[T1, TD2]耗时1飞机C窗口[T4, TD5]耗时1按最晚开始时间排序B的窗口最窄先排BB在1到2降落。然后是C窗口[4,5]跑道2空闲C在4到5降落。最后A在5到14降落可它的最晚开始时间TD1014显然超了判断为NO。但如果你换个顺序先让A在0到9降落B只能等窗口[1,2]已过也不行先让B在1到2A在2到11超窗口似乎这组本身无解。这里的关键是贪心判断的结果“NO”可能是对的但它的逻辑链条并不可靠换一组看起来差不多的输入就会错。网上很多博客说这道题按“最晚开始时间”排序就能过其实是他们用的测试数据恰好没踩到反例。我敢说你只过两项案例很可能就是踩了贪心的坑。搜索才是最稳的解法它不依赖任何排序假设会老老实实枚举每一种顺序并且通过剪枝快速排除明显无解的分支。1.3 正确思路状态是什么怎么转移正确做法是DFS回溯。我们维护一个当前“跑道可用时刻”cur它的初始值是0或者第一架飞机还没到时的某个空域时间。在递归每一层时从所有还没安排的飞机里挑一架计算这架飞机实际的开始降落时间。这里有个重要的点实际开始时间不是简单的T也不是简单的cur而是两者的较大值。记start max(T[i], cur)如果start小于等于T[i]D[i]说明这架飞机现在降落还来得及那就把这架飞机标记为已安排更新cur为start L[i]继续递归。如果某一层发现所有未安排的飞机都无法降落就回退到上一层尝试换一架飞机。为什么取max(T[i], cur)因为这架飞机不可能在它到达之前降落但跑道可能被之前那架飞机占用到很晚它也不可能在跑道空闲之前降落。所以它真正能开始降落的时刻一定是“自身就绪”和“跑道就绪”这两个条件都满足的时刻。这个看似简单的max恰恰是新手最容易写错的地方。很多人会直接写cur T[i] L[i]或者写cur cur L[i]这两种写法都没有正确处理“飞机还没到但跑道已经空了”的情况一遇到飞机之间有较大空闲时间结果就会错。2. 排查过程三种典型错误代码分析2.1 错误一把起点写成飞机到达时间而不是跑道可用时间有一种非常典型的错误写法核心代码长这样bool dfs(int dep, int cur) { if (dep n) return true; for (int i 0; i n; i) { if (used[i]) continue; if (cur p[i].t p[i].d) { // 只判断了当前跑道时间是否在窗口内 used[i] true; if (dfs(dep 1, cur p[i].l)) return true; // 直接拿 cur 加了 used[i] false; } } return false; }这段代码看着逻辑完整但它犯了一个关键错误它假设“当前跑道可用时间cur”就是“这架飞机开始降落的时间”所以直接拿cur去和窗口右端点比较并且直接把cur加上降落耗时。可如果cur远远早于飞机的到达时间T呢比如跑道第0时刻就空了而飞机第10时刻才到达那这架飞机实际开始降落时间应该是10不是0。你要是直接拿cur0去判断当然会错误地把一架明明可以在10时刻降落的飞机判定为“来不及了”。正确的判断必须写成int start max(cur, p[i].t); if (start p[i].t p[i].d) { ... }只要把这里改了很多“只过两项案例”的情况立刻会好转因为OJ的数据里几乎一定混入了这种“跑道空闲但飞机还没到”的用例你的错误写法会直接漏掉它们。2.2 错误二回溯时没有正确恢复状态第二个高频错误是状态恢复不完整。比如有人会把used数组在递归返回后忘记复位或者把cur作为全局变量在递归调用之后没有恢复到进入该层之前的值。举个常见写法bool dfs(int dep) { if (dep n) return true; for (int i 0; i n; i) { if (!used[i] max(cur, p[i].t) p[i].t p[i].d) { used[i] true; int old cur; cur max(cur, p[i].t) p[i].l; if (dfs(dep 1)) return true; used[i] false; // 这里恢复了used // cur 忘了恢复 } } return false; }这种写法里used数组恢复了但cur的值没有恢复。递归返回后cur很可能已经被某一个分支改成了很大的值再遍历其他分支时所有窗口都会被误判为来不及最终结果就是漏掉正确答案。修复方法很简单要么把cur作为递归参数传下去而不是全局变量要么在递归前保存旧值、递归后恢复。我个人的习惯是把cur写成dfs的参数这样每个递归分支都自带独立的cur根本不需要恢复也不容易出错。2.3 错误三剪枝或排序方向搞反还有一些人会在“优化”时把问题搞复杂。比如给飞机排序后发现过不了就怀疑排序不对于是换成另一套排序规则来回试。其实这道题的正解不需要对顺序做任何假设DFS天然会尝试所有可能。非要排序的话可以按窗口右端点升序作为启发式但注意这只能作为一种搜索顺序的优化不能改变判断结果更不能把“排序后线性扫描”当成最终算法。为什么排序优化有用因为DFS的搜索树会优先探索那些“最紧急、最容易导致无解”的飞机。如果先把窗口右端点小的飞机安排在靠前的位置一旦某架飞机实在安排不进去就能更快地发现整条路走不通从而剪掉大量无效分支。这个优化对性能有帮助但它的正确性依然由回溯保证而不是由排序本身保证。3. 正确实现与逐段讲解3.1 完整C代码下面是我后来修正并反复验证过的版本代码不长但每一个细节都值得仔细看#include bits/stdc.h using namespace std; struct Plane { int t; // 到达时间 int d; // 最大等待时间 int l; // 降落所需时间 }; int n; vectorPlane p; vectorbool used; bool dfs(int dep, int cur) { if (dep n) return true; for (int i 0; i n; i) { if (used[i]) continue; int start max(cur, p[i].t); if (start p[i].t p[i].d) continue; used[i] true; if (dfs(dep 1, start p[i].l)) return true; used[i] false; } return false; } int main() { int T; cin T; while (T--) { cin n; p.resize(n); used.assign(n, false); for (int i 0; i n; i) { cin p[i].t p[i].d p[i].l; } if (dfs(0, 0)) { cout YES\n; } else { cout NO\n; } } return 0; }这段代码的核心就是dfs函数。dep表示已经安排了几架飞机cur表示当前跑道处于空闲状态的时刻也就是跑道在这之前都被占用、从cur开始才可以使用。函数从所有未使用的飞机里遍历对每一架计算出start判断合法性然后递归。如果递归成功就立刻返回不需要继续找其他顺序。3.2 关键细节逐条解释第一为什么start max(cur, p[i].t)我已经反复强调过了这里再换个角度说跑道就好比一个会议室飞机就好比等待开会的团队每个团队有自己的“最早可入场时间”和使用时长。会议室可能从早上8点就空着但某个团队10点才能到那会议实际开始时间一定是10点而不是8点。计算机里的逻辑就是取两者较大的那个。第二为什么判断条件是start p[i].t p[i].d就跳过这等于说“这架飞机至少在start时刻才能开始降落但它最晚必须不晚于td开始”如果start已经超出了最晚开始时间那无论怎么等它都不可能合法降落了。第三为什么递归参数是start p[i].l而不是cur p[i].l因为跑道真正被占用的时间是“实际开始降落之后的那段时长”既然实际开始时间是start占用到startl这个时刻才释放下一架飞机当然要从这个释放时刻开始等。第四used数组必须在递归返回后复位。由于我们只求“是否存在一种顺序”只要找到一种就返回true所以没必要继续搜索。但如果在某条分支上找不到解那就必须把这架飞机“放回去”尝试下一个分支。不复位的后果我前面已经说了很多WA都是这么来的。3.3 可选的剪枝优化如果你觉得直接全排列性能太紧可以在主函数里先给飞机排个序按td最晚开始时间从小到大排。这个排序不会改变答案但会让DFS优先尝试“窗口更紧”的飞机往往能更快搜到答案或无解。代码只需要在main里加一行sort(p.begin(), p.end(), [](const Plane a, const Plane b) { return a.t a.d b.t b.d; });注意排序之后used数组和下标依然跟着排序后的p走不影响正确性因为我们的搜索遍历的是“当前所有未使用飞机”顺序无关紧要只影响搜索树遍历的先后。4. 为什么你的代码只能过两项案例问题排查速查表4.1 对照症状找原因我根据自己见过的大量相似提问整理了一个排查表。你可以对照自己的现状快速定位问题所在。症状最可能的原因修复方向样例全过提交只过两项其余WA跑道空闲Period与飞机到达时间没有取max直接拿cur判断或更新时间start max(cur, t[i])过两项其余TLE全排列没有剪枝或每次都从第0架重新扫描加窗口越界跳过continue必要时按最晚开始时间排序小数据能过n大了就挂递归层数太深状态恢复遗漏或代码里用了全局cur没回滚改成cur作为参数传递输出全是YES或全是NO把“最晚开始时间”误当成“最晚完成时间”仔细重新读题右端点是td不是tdl部分测试点出现非预期输出数组下标边界问题或者测试数据里有多个测试用例used和p没有清空每组数据重置used和vector这里最核心的一条就是绝大多数“样例过了但WA”的题问题都不是算法大方向错了而是某个边界条件或者状态转移的小细节错了。飞机降落问题尤其如此因为它看起来很简单简单到让人忽略max这个操作。4.2 通用调试技巧写个暴力对拍程序如果你按排查表改了还是过不了下一个建议是自己写一个绝对暴力的程序用来和你的主程序对拍。所谓“绝对暴力”就是不考虑任何优化直接枚举所有全排列把每一架飞机的降落序列固定下来然后按顺序模拟判断是否存在合法序列。比如在C里可以用next_permutation生成所有排列也可以嵌套DFS。然后随机生成数据把两个程序跑的结果做对比找到第一个不一致的数据再人工分析那组数据。我在修这道题时就用过这个办法。写一个工具函数bool check(vectorint order) { int cur 0; for (int idx : order) { int start max(cur, p[idx].t); if (start p[idx].t p[idx].d) return false; cur start p[idx].l; } return true; }再在主程序外层枚举所有order只要有一个order返回true就是YES。这个checker的正确性比你的DFS更容易验证因为它是朴素的模拟。然后用它跟dfs版本对跑数据规模在n10左右随机生成几百组一旦发现结果不一致立刻把输入打出来分析。这样做比盯着OJ的测试点猜原因高效得多。4.3 为什么“先排最紧急的”能大幅提速排序优化背后的道理是搜索树越早发现不可行分支越好。按最晚开始时间升序等于每一层都优先处理“如果不先安排它它就很容易过期”的飞机。这样做的效果是如果无解DFS往往在搜索树的较浅层就会碰壁从而剪掉大量深层递归。如果题目中的数据构造得比较阴间这个优化能把运行时间从几秒降到毫秒级。但要记住它只是启发式不是贪心算法。如果你的主逻辑只是“排序后依次判断”而没有回溯那等待你的只能是WA。5. 从这道题里能带走的通用经验5.1 做搜索题的三步自查法我现在做任何回溯题都会在下笔前先问自己三个问题。第一状态是什么在飞机降落问题里状态就是“当前已安排的飞机集合当前跑道可用时间”。第二转移是否覆盖了所有情况也就是每一层遍历所有未使用的飞机、计算真实开始时间、更新跑道时间这一步必须无遗漏。第三有没有冗余搜索像“如果当前这架飞机的窗口已经过了就直接跳过”就是典型的剪枝。这三个问题看着简单但能过滤掉大部分错误。很多人写代码属于“脑子跟手脱节”想到哪写到哪最后卡在案例上才回头看。我自己过去也这样后来养成了先口述一遍状态转移再写代码的习惯错误率低了很多。5.2 区间调度类问题的通用套路飞机降落问题其实是更广义的“单机调度问题”的一个特例。类似的问题还有给出一堆任务每个任务有最早开始时间、最晚开始时间、处理时长问能否全部完成。这类题有一个通用判断框架维护当前时间cur每次选择某个未完成任务用max(cur, earliest[i])作为实际开始时间判断是否在截止窗口内更新cur start cost[i]。一旦遇到无法安排的任务就回溯换顺序。以后你再去面试或者刷题看到这样表述的题目第一反应不应该是“排序贪心”而是“这题N是多少”。N小于等于15基本就是回溯或状态压缩DPN很大才需要想区间调度贪心或者线段树优化之类的更高级做法。这个判断习惯比记住这一道题的代码更有价值。5.3 踩过坑之后我对“等待”的理解题目里还有个容易误解的点飞机来了之后是可以“等一等”的最大等待时间D就是允许它在空中盘旋等待的时长。如果你把它理解成“地面等待”就会把整个系统弄混如果你把它理解成“必须在D内完成降落”又会把右端点算错。实际上它只是在等待“开始降落”的机会一旦开始L时间后落地。这个语义差异直接决定了判断条件到底是start td还是start l td。我见过好几个朋友都是栽在这里——他们以为飞机必须整个落地过程都在窗口内完成导致把很多明明有解的数据判断成无解。6. 最后的一点个人体会我修这道题的过程前前后后花了大概一个晚上。最难的不是写出DFS代码而是静下心来看清楚自己的错误到底在哪。当时我用对拍程序生成了几百组随机数据终于复现出那个“只过两项”的case发现是最开始把cur和飞机到达时间混用导致的。确实把max加上去之后一次提交就全绿了。现在回头看这道题其实给了我很深的影响。它让我明白OJ题目的测试点绝不是在为难你而是在为每一种常见的错误理解准备一个针对性用例。你能过哪几项基本能精确地映射到你代码里哪一处细节写错了。飞机降落问题教会我的不是DFS本身而是“当你的程序只过两项案例时大概率不是题目难而是你的一两个细节在骗你”。如果你现在也卡在这道题上建议按这个顺序排查先看start和max再看回溯状态再想窗口右端点最后再考虑优化。大概率很快就能看到YES的曙光。
阅读完成 · 觉得有帮助？
