2025年1月7日华为秋招非AI方向机考第一题是道100分的送分题滴滴预约单。题目看着是出行场景实际就是经典的区间调度贪心。我身边不少同学第一题反而没拿满不是因为不会贪心而是卡在输入解析和边界条件上非常可惜。这篇文章把题目还原、思路推导、Java/C/Python三套代码还有我实际踩过的坑一次说清楚。准备通软、嵌软、测试、算法、数据科学方向的同学都适合看完后直接抄作业。这道题从业务上看是滴滴司机接预约单本质上考察的是最基础的贪心算法和排序能力。华为机考是ACM模式需要自己处理输入输出跟LeetCode那种核心代码模式不一样所以不少人平时刷题没问题一上机就栽在BufferedReader和Scanner的选择上。下面我把这道题从头到尾掰开揉碎讲一遍。1. 真题背景与考点拆解1.1 华为秋招机考的题型分布华为的秋招机考一般是三道题分数分布通常是100分、200分、300分总分600分。第一题就是那个100分难度定位是“基础题”目的是筛掉完全写不了代码的人而不是拉区分度。真正的区分度在第二题和第三题但第一题的分数是保底丢了非常可惜。非AI方向通用软件、嵌入式软件、测试、算法、数据科学用的是同一套笔试题考察的是通用的算法基本功和代码能力不会专门偏向某个岗位方向。也就是说不管你投的是嵌软还是数据科学第一题都可能碰到这种看起来像业务题、实际上是经典算法模型的题目。我见过太多人第一题翻车了原因非常统一不是不会做而是不熟悉OJ在线评测系统的输入输出模式或者边界条件没想清楚。比如本场这道“滴滴预约单”有人把结束时间相同的订单排序方向搞反有人忘了处理“开始时间等于上一单结束时间”的情况还有人用Scanner读10万行数据直接超时。这些坑我都会在后面的章节里逐个拆开讲。1.2 “滴滴预约单”到底在考什么题目场景还原如下依据常见真题形态整理滴滴司机小张一天之内收到了N个预约订单每个订单有开始时间start和结束时间end时间单位是分钟取值在0到1440之间。司机同一时刻只能服务一个订单问小张这一天最多能完成多少个订单。输入格式第一行一个整数N表示订单数量接下来N行每行两个整数start和end。输出一个整数表示最多能完成的订单数量。这个题目包装了一层出行业务的外壳脱掉外壳以后就是一个非常经典的“最多不重叠区间数量”问题。会议室预定、课程安排、任务调度全都是同一个模型。华为把这种经典模型套一个业务场景来出题就是想看你能不能把实际问题抽象成算法问题这比死记硬背模板要重要得多。需要注意一个关键约定如果订单A的结束时间等于订单B的开始时间比如A是[1,3]B是[3,5]那这两个订单是可以连续接的。司机在3这个时刻已经服务完A可以立刻开始服务B。所以判断两个订单是否冲突要看的是next.start prev.end而不是next.start prev.end。这个细节我后面还会反复强调因为它在代码里就是一行符号的区别却是很多人的致命伤。2. 解题思路与算法设计2.1 把预约单抽象成区间模型每个订单都可以表示成一个区间[start, end]由于end时刻订单服务结束下一个订单可以在end时刻开始所以区间实际上是左闭右开[start, end)。我们需要从一堆区间里选出尽量多的区间要求它们两两不重叠。排序是这类问题绕不开的第一步。但按什么排序这是最容易纠结的地方。如果按开始时间排序直观上感觉“开始早的订单先处理”但这个直觉会出错。举个例子订单A是[0, 100]订单B是[1, 2]订单C是[2, 3]按开始时间排序会先选A结果只能接一单但如果先选B再选C能接两单。所以按开始时间排序是错的。正确做法是按结束时间排序。这个逻辑可以用一句话解释清楚一个订单结束得越早它给后面留下的时间窗口就越大优先选结束早的订单能容纳后续订单的概率就更高。这也是贪心算法在区间调度问题上的标准策略。推导到这里整个题目的主框架就出来了先把所有订单按end从小到大排序然后遍历排序后的订单维护一个变量lastEnd记录上一个已选订单的结束时间。如果当前订单的start大于等于lastEnd就选中它并把lastEnd更新为当前订单的end。2.2 贪心策略的直观理解与正确性很多人会问贪心算法只是“感觉对”怎么证明它一定对这里给一个不太严谨但很实用的解释方向交换论证法。假设存在一个最优解它选的第一个区间不是所有区间里结束时间最早的那个区间那么我们可以把这个最优解的第一个区间替换成结束时间最早的区间。替换之后因为最早结束区间的end不会比原来第一个区间的end更晚所以不会跟后面的区间产生新的冲突而且收益数量不变。这样一步步替换下去可以得到一个包含“结束时间最早区间”的最优解。不断对剩余区间重复这个过程贪心选择方案就能达到最优解。这个证明思路不用写在代码里但它能帮你确认自己不会用错贪心。说实话我在平时带人刷题的时候发现很多人遇到区间类问题第一反应是排序暴力枚举再优化一点能想到贪心但动手前从来不验证贪心的正确性。如果是在华为这种机考环境下一道100分的题你不需要太深的证明但至少要能举几个反例来验证自己的想法是否成立。另外要提醒的是这道题N的范围一般是1到100000如果用暴力枚举所有组合复杂度是指数级直接不可行。排序的复杂度是O(NlogN)遍历一次是O(N)整体O(NlogN)在10万数据量下没有任何压力。这也是为什么第一题通常只会考到排序、贪心、简单的数据结构而不会直接上复杂动态规划。2.3 带金额的进阶版本加权区间调度如果你在牛客或者其他平台刷到过这道题的变体可能会发现还有一版是每个订单带一个预估金额问最多能赚多少钱。这题就完全不一样了它不再是“最多能接几单”而是“收益最大化”贪心直接失效。举个例子订单A是[0, 10]金额100订单B是[0, 1]金额1订单C是[1, 10]金额1。如果按结束时间排序贪心会选B和C总收益2但最优解是选A收益100。贪心在这里就眼睁睁地错过最优解了。带金额的场景需要用到加权区间调度标准解法是动态规划加二分查找。先把区间按结束时间排序令dp[i]表示前i个订单能获得的最大收益。转移时有两种选择不选第i个订单收益就是dp[i-1]选第i个订单收益是当前订单金额加上“结束时间不超过当前订单开始时间”的前面所有订单的最大收益这个位置用二分查找找到。复杂度依然是O(NlogN)。我在本文的第3章会把不带金额的贪心版本用三种语言写出来这是100分题的标准解法。带金额的版本我会给出一个Java参考实现方便想深入一步的同学理解DP和二分如何结合。3. 三种语言实现与代码逐行解析3.1 Java 实现与输入优化Java的实现在思路上很直接重点是输入输出的写法。华为机考的数据量经常到10万行用Scanner读取会比较慢稳妥的做法是用BufferedReader加split切分。下面这版代码我建议直接背下来它适用于绝大多数笔试环境。import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); int[][] orders new int[n][2]; for (int i 0; i n; i) { String[] parts br.readLine().trim().split( ); orders[i][0] Integer.parseInt(parts[0]); orders[i][1] Integer.parseInt(parts[1]); } // 按结束时间升序排序 Arrays.sort(orders, (a, b) - a[1] - b[1]); int count 0; int lastEnd -1; for (int[] order : orders) { if (order[0] lastEnd) { count; lastEnd order[1]; } } System.out.println(count); } }这里有几个细节值得说。lastEnd初始化为-1是因为订单的start最小是0当第一个订单的start -1时必然成立。如果你初始化成0没问题因为start0恒成立但语义上不如-1清晰尤其在修改边界条件的时候容易出错。比较器(a, b) - a[1] - b[1]表示按数组第二列即end升序排列千万不要写反成b[1] - a[1]否则排序结果全反了。此外如果你平时习惯用int a Integer.parseInt(br.readLine())逐行读取这题老老实实一行一行读也够用不过用split( )切分时要注意一行开头结尾是否有空格。华为OJ的测试数据一般没有多余空格但加一个.trim()是成本极低的保险操作我建议保留。3.2 C 实现与代码细节C的实现里最常见的做法是用vectorpairint, int存储订单pair的first存startsecond存end排序时用lambda表达式按second升序排列。这里要特别提醒sort默认按pair的first排序所以如果直接sort(orders.begin(), orders.end())你其实是按开始时间排序结果就错了必须自己写比较逻辑。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairint, int orders(n); for (int i 0; i n; i) { cin orders[i].first orders[i].second; } // 按结束时间升序排序 sort(orders.begin(), orders.end(), [](const pairint, int a, const pairint, int b) { return a.second b.second; }); int count 0; int lastEnd -1; for (auto order : orders) { if (order.first lastEnd) { count; lastEnd order.second; } } cout count endl; return 0; }ios::sync_with_stdio(false);和cin.tie(nullptr);这两行是C选手在OJ上必须养成的习惯它们能显著加快cin和cout的速度。不加这两行在某些数据量较大的用例里可能会超时加了以后性能和scanf/printf基本持平。第一次见这段代码的同学可能会疑惑为什么要这样写简单说就是C的输入输出流为了兼容C标准IO默认做了同步关闭这个同步可以让输入输出更快。还有一个细节是lambda表达式的参数建议用const pairint, int避免无谓的拷贝。虽然这道题的数据量不至于因为拷贝超时但这是一个很好的代码习惯。最后lastEnd和count用int就足够了因为N最大10万答案不可能超过N不会溢出。3.3 Python 实现与性能说明Python最需要注意的是输入读取方式直接用input()在循环里读10万行是可行的但偏慢稳妥做法是用sys.stdin.buffer.read()一次性读入全部数据再统一切分。这个技巧在牛客和华为OJ上都非常实用。import sys def main(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) orders [] idx 1 for _ in range(n): start int(data[idx]) end int(data[idx 1]) idx 2 # 把end放在元组前面排序时可以直接按end升序 orders.append((end, start)) orders.sort() count 0 last_end -1 for end, start in orders: if start last_end: count 1 last_end end print(count) if __name__ __main__: main()这里最巧妙的地方是把(end, start)作为元组存储。Python元组排序默认按第一个元素升序再把end放在第一位这样一行orders.sort()就完成了按结束时间排序不需要写key参数。如果你非要用(start, end)的格式也可以写orders.sort(keylambda x: x[1])效果一样但会多一次lambda调用。在大数据量下直接把end放前面是更Pythonic也更快一点的做法。按end取出来之后遍历时用for end, start in orders解包注意变量顺序对应的是元组里的end和start写反了判断条件就错了。这是很多Python选手容易犯的低级错误。3.4 三语言实现与核心差异三份代码解决的是同一个问题核心逻辑完全一样按结束时间排序遍历时维护lastEnd选出startlastEnd的订单。差异主要集中在这几个方面语言输入优化方式排序写法常见风险JavaBufferedReader splitArrays.sort 自定义比较器比较器方向写反Cios::sync_with_stdio(false)sort lambdapair默认按first排序Pythonsys.stdin.buffer.read().split()orders.sort() 配合元组结构调整解包时变量顺序写反从我自己的刷题经验看如果你擅长C笔试时用C是最稳的代码量短、性能好Java的优势在于熟悉的同学多但要注意输入输出别拖后腿Python写起来最省事适合快速验证思路但在某些要求高性能的场景下要谨慎。好消息是这道题的复杂度是O(NlogN)Python完全扛得住不会出现Python被卡常的情况。如果答题时间充裕我建议你用Python先跑一遍思路验证正确性再用自己最熟练的语言写正式提交版本。这样做看起来多花了时间实际上能帮你提前发现边界条件上的逻辑漏洞反而省下反复提交试错的成本。4. 在线测试与踩坑实录4.1 边界条件这些用例最容易翻车我整理了几个我实际带人刷题时经常会遇到的测试用例。建议你把每份代码都跑一遍这些用例对照期望输出检查自己的逻辑。输入期望输出说明1 对 start0, end5 的单个订单1最小规模验证基本逻辑订单依次为 [1,3] [3,5] [5,7]3后单开始时间等于前单结束时间可连续接订单依次为 [1,4] [2,3] [3,5] [4,6]2有部分重叠贪心应选 [2,3] 和 [4,6] 或类似组合所有订单都重叠如 [1,10] [2,11] [3,12]1只能选一个大量订单结束时间相同取决于开始时间排序稳定性不影响结果但要注意遍历顺序最后一种情况值得多说两句。比如订单是[1,5]、[2,5]、[3,5]结束时间都是5排序后它们之间的顺序无所谓因为只要选了第一个lastEnd变成5后面两个的start分别是2和3都小于5全部被跳过。结果还是1不会受影响。所以你不需要操心同结束时间的订单内部如何排列只要保证整体按结束时间升序即可。4.2 常见错误与修正思路我总结了几类常见错误都是我在实际辅导中反复见到的每条都对应真实的翻车场景。第一类是排序方向错误。有人会想当然按开始时间排序然后输出一个看起来很合理的答案。建议遇到区间调度问题先默念三遍“按结束时间排序”这个条件反射能救你不少分。第二类是边界条件判断错误。判断条件写成order[0] lastEnd而不是order[0] lastEnd这样会漏掉“开始时间等于上一单结束时间”的可接订单。是否应该取等号一定要在看题时确认清楚不要凭感觉。第三类是输入处理问题。Java的Scanner在10万行输入下会慢Python的input()在循环里多次调用也会慢。这类问题平时在本地IDE跑完全测不出来一上OJ就容易超时所以从现在开始就养成用高速读入的习惯。第四类是忘记处理N0。虽然题目通常会说1 N 100000但如果你在本地自测时敲一个空行程序可能直接数组越界或者解析异常。建议在代码开头加一个if (n 0) return;的防御性判断成本极低但能避免一些奇怪的运行时错误。4.3 如何在在线OJ上验证你的代码华为机考系统里没有本地调试器你在编辑器里写完代码直接提交。这种情况下最稳妥的验证流程是先在本地把示例输入跑一遍再跑几个自己构造的边界用例最后再提交。很多人省掉第二步直接提交结果就是反复编译错误、运行错误、答案错误白白浪费提交次数。在线OJ上遇到“答案错误”时千万不要盲目改代码。第一步先检查自己的输出格式会不会多了空格或换行第二步检查排序和判断条件用最小用例在草稿纸上手算一遍对比程序输出第三步再考虑算法思路是否正确。这三步能覆盖绝大多数错误场景。我平时练习时还有一个习惯写一个暴力解法作为对数器随机生成小规模数据把贪心解和暴力解的结果对比。虽然笔试时没有条件这么做但平时用这个方法来验证贪心思路是否正确特别有效。等你练到对贪心模型足够熟悉考场上一眼就能判断这类题能不能用贪心自然就不需要每次都对数器验证了。关于代码风格华为OJ对Java主类名要求是MainC的main函数返回值必须是intPython则没有特殊要求。这些细节看起来不起眼真到考场上忘了就会直接编译失败非常影响心态。建议在正式机考前用牛客或者华为官方模拟环境完整走一遍流程熟悉从打开题目到提交代码的每个步骤。回到这道“滴滴预约单”我个人在实际操作中的体会是第一题最大的敌人不是算法而是粗心。这题考的知识点你在任何一本算法书里都能找到但能把边界条件、输入输出、排序方向全部处理对才体现出真实的工程习惯。华为这类大厂的笔试第一题拼的不是智力而是稳定性和细节把控。平时刷题时多花30秒检查一遍边界条件比考场上多试错三次要划算得多。最后再分享一个小技巧区间调度类题目如果题目里出现了“最多能完成多少个”“最多能安排几场”这类描述十有八九是贪心加排序如果出现了“最大收益”“最大价值”这类描述通常要往动态规划方向想。把这个规律记在脑子里下次遇到类似的业务包装题你就不会慌。