如果你准备过2023届的阿里秋招笔试大概率对那套题有印象笔试时长90分钟前面是几道选择题后面跟着三道编程题难度从2星一路拉到4星。最后那道4星压轴题往往是整场笔试真正拉开差距的地方。很多人前面顺风顺水一到压轴题就开始卡不是完全没思路而是半天读不懂题目到底在考什么。这篇文章我拿一道2023年阿里笔试里非常典型的4星题来完整复盘一遍题目内核是“带权区间调度”外衣是直播推荐位排期。这道题在当年多个批次的笔试里都出现过变体非常适合用来理解阿里4星编程题的出题套路和应对方式。1. 阿里编程题的星级体系到底怎么理解1.1 不是所有4星题都难到劝退阿里的在线笔试一般通过牛客网进行题目会被标记成1到5星。这套星级不是随便标的基本可以理解为面试官对这道题所覆盖知识深度和代码量的预估。1星题是送分题2星题考基础3星题开始有点门槛4星题已经能拦住相当一部分候选人5星题则属于竞赛级别笔试里通常不会大量出现即使出现也往往作为拉分区分的压轴。我见过不少同学把4星题当成“劝退题”一看到星标就发怵。实际参加过以后你会发现4星题和3星题的区别通常不在于思维跨度有多大而在于它需要你多走一步把已知的算法模型和题目场景结合再处理掉一两个边界细节最终给出一段比较干净的代码。它会考察你是否能在有限时间内把一个业务描述翻译成数据结构与算法的语言。1.2 4星题的常见题材和考察方向从2021年到2023年的真题来看阿里笔试的4星压轴题基本集中在几类模型上区间调度与区间DP、贪心加数据结构优化、二分答案加检验、图论建图加最短路径或拓扑排序、以及带约束的背包或状态压缩DP。这些模型有一个共同点它们都可以用一道简单的暴力题作为垫脚石然后靠数据范围逼迫你优化到O(n log n)或O(n)级别。为什么阿里的4星题偏爱这些方向因为阿里的业务线涉及电商、直播、物流、本地生活很多真实问题天然带时间窗口、资源冲突、容量限制这些约束。把一道区间调度题包装成“直播推荐位排期”或者把带约束的贪心包装成“仓库拣货路径”对出题人来说是成本很低的事情对候选人来说却是最真实的压力测试。1.3 一道题的价值不只是入场券4星压轴题在整场笔试里占的分值比例很高一道题往往相当于前面两三道题的总和。如果你的目标是拿到面试邀约前面的2星和3星题必须保证尽量全对4星题只要能通过一部分测试点就可以在排名上跑赢很多人。也就是说你不需要把这类题做得完美但也不能交白卷。哪怕只能写出暴力解也要把所有能拿的分拿满。这也是我写这篇复盘的原因压轴题决定的是上限而绝大多数候选人并不是输在智商而是输在没有系统地理解4星题的常规套路。2. 原题还原把直播推荐位排期翻译成区间调度2.1 这是一道典型的业务包装题完整题目我不可能一字不差地背出来但算法内核我记得非常清楚。2023年某场笔试的4星题大意是这样的双11大促期间直播间的推荐位每一个时刻只能展示一条短视频。运营团队准备了N条商品短视频第i条视频从时刻L_i开始播放会在时刻R_i结束这里要特别注意区间是左闭右开定义的也就是说[L_i, R_i)表示视频在L_i时刻开始一直播放到R_i时刻之前结束R_i时刻可以被下一条视频使用。如果某条视频被选中平台预计能获得V_i元的成交额。视频一旦选中就必须完整播放同一时刻不允许两条视频同时占住推荐位。现在的问题是如何选择视频能让平台获得最大的总成交额。2.2 输入输出和数据范围因为是在线笔试输入输出格式和边界条件也是考察点之一。典型的输入格式是第一行一个整数N接下来N行每行三个整数L_i、R_i、V_i。数据范围一般是1 N 10^50 L_i R_i 10^91 V_i 10^9。输出一个整数表示最大成交额。这个数据范围非常关键。N到了10^5的量级意味着任何O(n^2)级别的算法都会超时更不用说枚举子集的O(2^n)了。V_i到10^9意味着收益累加以后轻松超过int的表示范围如果你还用int去存答案后面几个测试点一定WA。2.3 一个例子看懂题目在说什么为了说明白我写一个简单样例输入 4 1 3 5 2 5 6 4 6 8 6 7 4这组数据里视频A从时刻1播到3预计收益5视频B从2播到5预计收益6视频C从4播到6预计收益8视频D从6播到7预计收益4。如果只挑收益最大的视频B收益是6但它和A、C都冲突选了它就只能放弃A和C。最优的选法其实是选A、C、D三段时间分别是[1,3)、[4,6)、[6,7)完全不重叠总收益是58417。这就是一个典型的“局部最优不等于全局最优”的例子也是这道题最有意思的地方。2.4 从题面里提炼出三个建模要点第一每一条视频可以看成数轴上的一个区间左端点是开始时间右端点是结束时间收益是区间权重。第二“同一时刻不能同时播放”这个约束翻译过来就是“任意两条被选中的区间不能重叠”。第三题目要求最大化收益总和这就成了标准的带权区间调度问题。这三个要点一旦想清楚题目就从一段双11讲故事的文字变成了一个可以被算法处理的数学模型。后面所有步骤都是在这个模型上展开的。3. 思路递进从暴力枚举到动态规划3.1 暴力为什么一定不行最快想到的解法是枚举所有视频子集然后检查选出来的视频是否两两不重叠。N4的时候这一共只有16种情况手算都能算出来。但N到了10^52^N这个数字已经大到没有讨论的意义连N30都跑不动更不用说大数据测试点了。还有一个稍微聪明一点的暴力是DFS回溯尽量剪枝本质上仍然是指数级复杂度。笔试环境里时间和内存都有严格限制这种解法只能拿到很小的部分分。如果你只追求过几个样例可以写但千万不要在考场上指望它AC。3.2 为什么“按收益排序然后贪心”会翻车我第一次看到这道题脑子里冒出的第一个想法是把视频按收益从大到小排每次尽量选收益最大的如果不冲突就选上。这个想法非常自然但它是错的。回到刚才那个样例收益最大的是视频B收益6。如果按收益从大到小选先把B选了再想选A发现时间覆盖了想选C也覆盖了最后只能配一个D总收益只有10。但最优答案是17。问题在于选一条收益高的视频可能堵住了后面好几条收益中等的视频的去路而放弃一条局部收益高的视频换来的是更多视频的组合收益。这类问题之所以不能直接贪心是因为区间之间的冲突关系不是局部的、可恢复的前面选得急后面就失去选择空间。对这类“选择互相排斥的资源来最大化总价值”的问题动态规划是更可靠的思路。3.3 关键一步按右端点排序动态规划的第一步是确定状态顺序。区间问题里最经典的排序依据是右端点。为什么是右端点而不是左端点因为区间是否重叠本质上取决于当前区间的开始时间和之前区间的结束时间之间的关系。如果按右端点从小到大排序我在处理第i个区间时前i-1个区间的结束时间都不超过第i个区间的结束时间。这样一来如果要选第i个区间我能知道它前面的可用状态是什么只需要找到一个位置p使得位置p之前的所有区间都和当前区间不重叠也就是第p个区间的右端点小于等于当前区间的左端点。这个位置之后的所有区间因为右端点都比当前区间左端点大无法和当前区间共存。排序的作用是让区间之间的“前后关系”变得清晰让DP可以从左到右顺序计算而不需要回头去比较每一对区间是否冲突。3.4 状态设计与转移方程设dp[i]表示“按右端点排序后前i个区间也就是从第0个到第i-1个内能获得的最大收益”。注意这里我用的是前i个下标可以从0开始也可以从1开始只要自己别搞混就行。对于第i-1个区间假设0-based它有两个选择不选它那么当前收益就是dp[i-1]选它那么它之前可以兼容的最大前缀是第p个区间收益是dp[p]V。整理成转移方程就是dp[i] max(dp[i-1], dp[p] V_i)p是通过二分查找得到的在所有已经排序的区间中找到最后一个满足R[j] L_i的下标j那么p j1因为dp[p]表示前p个区间的最大收益下标0到p-1都在可选集合里。这个方程看起来简单但它的正确性依赖一个很重要的性质无后效性。已经计算好的dp[p]只代表前p个区间内部的最优组合它不会因为后面选了第i-1个区间而改变。前面再怎么选都不会影响第i-1个区间和更早区间是否兼容因为时间方向是单向的。3.5 用样例手推一遍DP拿前面的样例按右端点排序后是区间1[1,3) 收益5 区间2[2,5) 收益6 区间3[4,6) 收益8 区间4[6,7) 收益4对区间1前面没有可兼容前缀dp[1] max(0, 05) 5。对区间2L2找到最后一个R2的区间没有所以dp[2] max(dp[1]5, 066) 6。对区间3L4最后一个R4的是区间1所以dp[2]是前缀收益5dp[3] max(6, 5813) 13。对区间4L6最后一个R6的是区间3所以dp[3]13dp[4] max(13, 13417) 17。答案就是17。手动推完这个过程整个DP模型就不再是抽象的公式而是一个可以放心实现的算法了。4. 手把手实现C完整代码与易错点4.1 一份可以直接跑通的完整代码核心代码不长我用C17来写#include bits/stdc.h using namespace std; struct Item { long long l, r, v; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorItem a(n); for (int i 0; i n; i) { cin a[i].l a[i].r a[i].v; } // 关键步按右端点从小到大排序 sort(a.begin(), a.end(), [](const Item x, const Item y) { return x.r y.r; }); // ends[i] 存 a[i].r因为 a 已按 r 排序所以 ends 单调不减 vectorlong long ends(n); for (int i 0; i n; i) { ends[i] a[i].r; } vectorlong long dp(n 1, 0); for (int i 1; i n; i) { // 当前要考虑的区间是 a[i-1] long long L a[i - 1].l; long long V a[i - 1].v; // 在 ends[0..i-2] 中找最后一个 L 的位置 int k upper_bound(ends.begin(), ends.begin() i - 1, L) - ends.begin(); // 此时 k 表示前 k 个区间的右端点都 L long long take dp[k] V; // 选当前区间 long long skip dp[i - 1]; // 不选当前区间 dp[i] max(take, skip); } cout dp[n] \n; return 0; }这段代码实测可以通过N10^5级别的随机数据。如果你把V_i的类型写成int最后的dp结果很可能是错的因为10^9乘以10^5会溢出int。V_i、L_i、R_i、dp数组全部用long long是最稳妥的做法。4.2 代码里最容易写错的两个细节第一个细节是upper_bound的范围。很多人在考场上一着急就写upper_bound(ends.begin(), ends.end(), L)把整个数组都搜了一遍。但当前处理到第i个区间时能作为前缀的只有前i-1个区间的右端点第i个及之后的右端点虽然已经排序但它们对应的区间还没有被DP计算过如果把它们也包括进来take值就会错误地利用未来信息导致答案偏大。第二个细节是dp下标和区间下标的转换。我上面用dp[i]表示前i个区间所以区间a[i-1]对应dp中位置i。二分找到的k表示“右端点L的前缀长度”那么选当前区间时的前缀收益就是dp[k]这个对应关系一旦想明白代码就不容易错了。我建议在写代码时把注释写清楚因为笔试时会受到时间压力清晰的注释能帮你少犯低级错误。4.3 复杂度分析排序是O(n log n)每个区间做一次二分查找是O(log n)总体时间复杂度O(n log n)空间复杂度O(n)。对于N10^5来说这个复杂度在2秒的时限内完全没问题。即使N放大到10^6只要常数写得好理论也能跑完只是内存占用会稍微高一些。4.4 拓展如果题目要求输出选了哪些视频有的变体题会要求输出方案而不仅仅是最大收益。这时候只要增加一个记录数组from[i]表示dp[i]是从哪个状态转移过来的。具体做法是vectorint from(n 1, 0); vectorint pre(n 1, -1); for (int i 1; i n; i) { int k upper_bound(ends.begin(), ends.begin() i - 1, a[i - 1].l) - ends.begin(); long long take dp[k] a[i - 1].v; long long skip dp[i - 1]; if (take skip) { dp[i] take; from[i] 1; // 表示选了当前区间 pre[i] k; // 上一状态是前 k 个区间 } else { dp[i] skip; from[i] 0; // 表示跳过当前区间 pre[i] i - 1; } } vectorint chosen; for (int i n; i 0; ) { if (from[i] 1) { chosen.push_back(i - 1); // 区间编号 i pre[i]; } else { i pre[i]; } } reverse(chosen.begin(), chosen.end());这种路径恢复思路在很多区间DP题里通用建议在考场上用纸笔先画一个小例子确认from和pre的取值逻辑再写代码。5. 实战中的避坑笔记这些坑我都踩过5.1 对“左闭右开”的理解不能含糊区间是[L, R)还是[L, R]直接决定二分查找的比较符号。如果是左闭右开那么前一个区间的结束时间等于后一个区间的开始时间时两个区间可以无缝衔接所以条件是用R小于等于L来判断不重叠。如果是闭区间同样的条件就会导致边界重叠答案会偏小或偏大。我在实际笔试时习惯用“结束时间点属于前一个区间不属于后一个区间”来理解左闭右开。这样在判断两个区间是否重叠时就不容易出错了。如果题目没有明确说明区间开闭我建议在解题前先给自己写一句话标注清楚。5.2 二分边界和下标换算是最容易出bug的地方有一个极端情况要特别注意如果当前区间的左端点L比所有已有区间的右端点都小比如第一个区间的L0那upper_bound返回0take dp[0] V这是正确的。如果L比所有已有区间的右端点都大比如最后一个区间的L非常大那upper_bound返回i-1take dp[i-1] V这也对。最容易出问题的是用end()而不是begin()i-1以及把upper_bound的返回值直接当成前缀长度而不做减一处理。我的建议是先把dp下标含义写清楚然后用一个小样例手算一遍再提交。5.3 超时和内存问题排查思路如果在牛客网提交后发现超时先检查是不是用了cin而没有关同步。代码里写着ios::sync_with_stdio(false)和cin.tie(nullptr)一般就够用了。如果还是慢可以考虑把输入改成scanf或者用快速读入模板但绝大多数情况不需要。内存方面dp和ends各占8N字节N10^5时占用很小。如果题目数据范围到了10^6vector的扩容和拷贝可能会带来短暂内存峰值可以使用reserve提前预留容量。5.4 用对数器验证自己的代码我在做题时养成一个习惯写完正解后立刻写一个非常暴力的对照程序然后随机生成小数据跑几千组对比。对于这道题暴力程序可以这样做long long brute(vectorItem a) { int n a.size(); long long ans 0; for (int mask 0; mask (1 n); mask) { long long sum 0; bool ok true; for (int i 0; i n ok; i) { if (!(mask i 1)) continue; sum a[i].v; for (int j i 1; j n ok; j) { if (!(mask j 1)) continue; if (a[i].l a[j].r a[j].l a[i].r) ok false; } } if (ok) ans max(ans, sum); } return ans; }这个暴力写法只适合N15的小数据但它能帮你确认DP实现没有细节错误。随机生成一百组数据正解和暴力结果全部一致我才会真正放心提交。6. 从一道4星题复盘这一类压轴题背后的能力模型6.1 一道题考察了哪些基本功这道4星题表面上只考了一个带权区间调度DP但它实际串联了四个基本功建模能力、排序思维、二分查找的熟练度、以及long long和边界处理等代码素养。阿里4星题极少单独考一个孤立知识点它更喜欢把两三个基础模型缝合在一起用业务场景做包装。换句话说如果你的排序、二分、DP基础都扎实4星题并没有想象中那么恐怖。反过来如果这三样里有一项不熟你很可能在做题时卡在一个小步骤上比如找不到p的位置然后整个思路断掉。6.2 阿里笔试的时间分配建议以90分钟笔试为例我比较推荐的分配是前10分钟做选择题和简单题中间35分钟做两道中等题最后30到40分钟留给4星题如果最后还剩时间再回头检查前面有没有低级错误。如果4星题卡了超过15分钟还没有一点头绪可以先写一个暴力解至少保证拿部分分。别在4星题上死磕太久。一道题占的分再高如果耗费了整个后半场还写不对性价比远低于把前面题检查一遍。我见过有人前面两道题没有全对最后一道压轴题却花了大量时间结果笔试整体分数并不理想。6.3 针对性刷题建议如果你想专门准备这一类4星题我的建议不是盲目刷题而是按模型组题练习。区间调度类可以重点做这些方向无权重区间调度求最大数量、带权区间调度求最大收益、区间分组、区间覆盖最少数量、以及区间内的二分优化。力扣上经典的1235题“规划兼职工作”和今天这道题几乎是同构的建议作为入门题先吃透。其他4星常考模型也要建立自己的模板贪心加优先队列的题目、二分答案的题目、拓扑排序的题目。每类模板不需要背很多道题但每一道都要能独立推导、独立写完并解释清楚为什么这样贪心或DP是对的。6.4 考前一周的心态调整临考前一天不建议再刷新题而是把做过的题目按模型重新过一遍尤其是自己写过的代码。你会发现很多题目之间是有规律可循的比如今天这道带权区间调度和另一道“最多能安排多少场会议”的题目排序方式和冲突判断很相似只是状态设计和转移方程不同。我在实际备考时还有一个习惯把每类模型的“判断标志”记下来比如看到“同一时刻只能一个”、“最大化总和”、“N达到10^5”立刻联想到排序加DP看到“每个区间最多选一次且要覆盖一段范围”就考虑贪心加堆。这种条件反射不是天生的是靠反复练习形成的。最后再分享一个个人感受4星压轴题最大的敌人不是算法本身而是你在考场上对未知题目的恐惧。很多题只要你静下心来把样例手算一遍把数据范围瞄一眼就成功了一半。像今天这道题核心代码不到40行难的是从一堆业务描述里提炼出区间调度模型。希望这篇复盘能让你下一次看到类似的题目时心里有一个清晰的做题路径。