如果你准备过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^5，0 <= L_i < R_i <= 10^9，1 <= 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)，完全不重叠，总收益是5+8+4=17。这就是一个典型的“局部最优不等于全局最优”的例子，也是这道题最有意思的地方。
2.4 从题面里提炼出三个建模要点
第一，每一条视频可以看成数轴上的一个区间，左端点是开始时间，右端点是结束时间，收益是区间权重。第二，“同一时刻不能同时播放”这个约束，翻译过来就是“任意两条被选中的区间不能重叠”。第三，题目要求最大化收益总和，这就成了标准的带权区间调度问题。
这三个要点一旦想清楚，题目就从一段双11讲故事的文字，变成了一个可以被算法处理的数学模型。后面所有步骤都是在这个模型上展开的。
3. 思路递进：从暴力枚举到动态规划
3.1 暴力为什么一定不行
最快想到的解法是枚举所有视频子集，然后检查选出来的视频是否两两不重叠。N=4的时候，这一共只有16种情况，手算都能算出来。但N到了10^5，2^N这个数字已经大到没有讨论的意义，连N=30都跑不动，更不用说大数据测试点了。
还有一个稍微聪明一点的暴力是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 = j+1（因为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, 0+5) = 5。对区间2，L=2，找到最后一个R<=2的区间，没有，所以dp[2] = max(dp[1]=5, 0+6=6) = 6。对区间3，L=4，最后一个R<=4的是区间1，所以dp[2]是前缀收益5，dp[3] = max(6, 5+8=13) = 13。对区间4，L=6，最后一个R<=6的是区间3，所以dp[3]=13，dp[4] = max(13, 13+4=17) = 17。
答案就是17。手动推完这个过程，整个DP模型就不再是抽象的公式，而是一个可以放心实现的算法了。
4. 手把手实现：C++完整代码与易错点
4.1 一份可以直接跑通的完整代码
核心代码不长，我用C++17来写：
#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; vector<Item> 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 单调不减 vector<long long> ends(n); for (int i = 0; i < n; ++i) { ends[i] = a[i].r; } vector<long 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; }这段代码实测可以通过N=10^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)。对于N=10^5来说，这个复杂度在2秒的时限内完全没问题。即使N放大到10^6，只要常数写得好，理论也能跑完，只是内存占用会稍微高一些。
4.4 拓展：如果题目要求输出选了哪些视频
有的变体题会要求输出方案，而不仅仅是最大收益。这时候只要增加一个记录数组from[i]，表示dp[i]是从哪个状态转移过来的。具体做法是：
vector<int> from(n + 1, 0); vector<int> 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; } } vector<int> 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比所有已有区间的右端点都小，比如第一个区间的L=0，那upper_bound返回0，take = dp[0] + V，这是正确的。如果L比所有已有区间的右端点都大，比如最后一个区间的L非常大，那upper_bound返回i-1，take = 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字节，N=10^5时占用很小。如果题目数据范围到了10^6，vector的扩容和拷贝可能会带来短暂内存峰值，可以使用reserve提前预留容量。
5.4 用对数器验证自己的代码
我在做题时养成一个习惯：写完正解后，立刻写一个非常暴力的对照程序，然后随机生成小数据跑几千组对比。对于这道题，暴力程序可以这样做：
long long brute(vector<Item>& 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; }这个暴力写法只适合N<=15的小数据，但它能帮你确认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行，难的是从一堆业务描述里提炼出区间调度模型。希望这篇复盘能让你下一次看到类似的题目时，心里有一个清晰的做题路径。
