距离美团2023校招技术岗第9场笔试结束已经有一段时间但三道题当时带给我的冲击感到现在还记得。这场笔试的题面几乎每一道都套了一层业务壳骑手怎么接单、门店评分怎么调、配送站点上的包裹怎么取。剥开壳之后你会发现考的全是算法题里最常被忽略的底层模型——贪心加反悔堆、差分数组、树上依赖背包。这篇文章把这三道题完整地复盘了一遍既给出了我能跑通的实现也把推导过程中的关键想法和踩坑点一起写了出来。不管你是正在备战校招的应届生还是想补一补算法基础的工程师这套题都值得认真过一遍。1. 第9场笔试的整体印象三题分布与美团出题口味1.1 题量、时长与难度梯度这场笔试我记忆里是120分钟三道题全部是ACM风格的输入输出也就是你得自己处理标准输入、自己输出结果。第一题只要掌握贪心加一个优先队列就能拿下但前提是你得意识到直接按截止时间排队这个朴素做法是错的。第二题考的是差分数组如果你没见过这类模型很容易把问题想复杂甚至去写线段树然后越写越慌。第三题是树上依赖背包难度直接拉满我身边能当场AC的人不多大多数人是暴力枚举部分用例拿分。从分值分布来看三题的分值并不是平均的越往后分值占比越大。这意味着即便前两题全对第三题只过一半用例总分也可能被拉开很远。美团笔试的系统是按通过用例数给分的所以能拿部分分一定要拿空题是零分暴力骗分不丢人。1.2 美团出题的一个明显偏好业务壳很厚这三道题没有一道是直接说给你一个数组请做某某操作也没有请默写最短路模板。每道题都包了一层业务场景骑手配送、门店经营调整、配送网络取件。这是美团出题的一贯风格也可以理解为面向业务的技术团队在筛选候选人时的价值取向——算法能力强同时也要能快速把业务问题翻译成数学模型。我经常跟准备校招的朋友说看到这种故事很长、数据范围写在最后的题目第一件事不是逐字读故事而是先扫一眼数据范围再找题目最后那句求什么。数据范围直接告诉你复杂度上限求什么决定算法方向。这两个信息拿到手场景描述里的大部分话术就可以暂时忽略。1.3 横向对比第9场相比其他场次难在哪网上能搜到的其他场次题目有些第一题就是普通数组操作、字符串判断第二题是二叉树层序遍历第三题是最短路或并查集。第9场这场不一样第一题就不是纯送分而是朴素贪心选不出来、需要反悔的经典模型第二题如果没听过差分会卡很久第三题又把树形DP和背包结合三个知识点叠在一起。从我复盘的角度看这套题的区分度设计得相当好。它没有考冷门算法考的全是高频模型但高频模型嵌套到业务场景里难度立刻上一个台阶。而且三道题的模型几乎没有重复覆盖了贪心、差分、树DP三个方向基本把校招算法笔试的主干考了个遍。2. 第一题先送哪单不超时堆加贪心才是正解2.1 还原后的题面某外卖平台有 n 个待配送订单第 i 个订单骑手需要耗时 time_i 才能完成配送用户期望在 deadline_i 时刻之前含收到餐。骑手一次只能配送一个订单两个订单之间切换不耗时骑手从 0 时刻开始工作。请计算骑手最多能让多少个订单按时送达。输入第一行一个整数 n1 n 100000。接下来 n 行每行两个整数 time_i 和 deadline_i1 time_i, deadline_i 1e9。输出一个整数表示最多能按时送达的订单数。刚看到这个题时我的第一反应是这不就是按截止时间排序然后顺序做吗。但构造一个反例就能推翻订单 A 耗时 3、截止 4订单 B、C、D 各耗时 1、截止 5。按截止时间排序后A 排在前面如果先做 A到时刻 3 完成后面只有 B 能在时刻 4 完成C、D 都超时最多 2 单。但如果你跳过 A先做 B、C、D三个都能在截止时间内完成最多 3 单。这个反例说明了一个关键结论这类调度问题里单纯按截止时间贪心不够因为先做的订单可能会挤掉后面多个更短的订单。我们需要在决策过程中允许反悔——把已经选中的、耗时最长的订单踢出去给后面更优的订单腾位置。2.2 最大堆替换法的推导与证明正确做法分两步。第一步把所有订单按 deadline 从小到大排序。第二步维护一个已选订单耗时的大根堆同时维护当前已选订单的总耗时 cur。每扫描到一个新订单先把它的耗时 t 入堆、cur 加上 t如果此时 cur 已经超过了当前订单的 deadline就把堆里耗时最大的订单移出cur 减去该耗时。为什么第一步要按截止时间排序因为我们每一步都在考虑截止时间最早的订单希望优先满足时间压力更大的订单而反悔操作保证了已经选中的集合始终是在前 k 个订单里能按时完成且总耗时最小的集合。换句话说扫描到第 i 个订单时堆里的集合就是前 i 个订单中最多能按时完成的那一组且该组总耗时是所有同等数量方案里最小的。这个不变量是整个反悔贪心正确性的基石。为什么踢掉最大的就是对的因为踢掉一个耗时大的订单cur 的下降量最大腾出的时间最多能容纳后续更多订单而总订单数在先加入再删除的过程中保持不变只换不增所以不会因为踢错了导致数量减少。这个技巧在很多文章里叫反悔堆在力扣上对应课程表 III这道题本质上是同一个模型。只要你能把这个模型和外卖配送场景对应上代码就是十分钟的事。2.3 边界情况与复杂度分析所有数字都是正整数所以不需要考虑 0 时刻和负截止时间。n 最大是 1e5排序 O(n log n)堆操作每个订单入堆出堆最多一次总复杂度 O(n log n)空间 O(n)。这里有个容易忽略的点cur 要用 long long虽然单个 time_i 只有 1e9但 n 个累计起来会超过 2^31-1int 溢出后 cur 可能变负数判断cur deadline会直接失灵。这个坑我在考场踩过后来凡是累计求和的变量一律 long long 起步。2.4 可运行的实现代码#include bits/stdc.h using namespace std; int main() { int n; scanf(%d, n); vectorpairlong long, long long a(n); // first: deadline, second: time for (int i 0; i n; i) { scanf(%lld%lld, a[i].second, a[i].first); } sort(a.begin(), a.end()); priority_queuelong long pq; // 大根堆 long long cur 0; for (auto p : a) { long long t p.second; pq.push(t); cur t; if (cur p.first) { cur - pq.top(); pq.pop(); } } printf(%zu\n, pq.size()); return 0; }这个题用 Python 写也很简单但要注意heapq默认是小根堆想取最大值要么存负数要么用heapq.nlargest再手动改写法上比 C 烦一点。笔试时如果输入规模大Python 的heappush和heappop是 O(log n)1e5 的数据也能过不用担心超时