前两天一个学弟跟我吐槽说华为OD机考双机位一开整个人紧张到鼠标都快握不住了结果题目发下来一看什么“最佳升级时间窗”第一眼像产品经理写的需求文档第二眼才知道又是区间题。我听完就笑了因为这种题在OD机考里真的太典型了题面包装成业务场景骨子里考的就是经典算法。今天我就借这道题把从读题到AC的完整过程拆开讲一遍顺便把双机位考试的操作细节、Java实现、考场踩坑一起聊透给准备OD机考的朋友一份能直接照着练的思路。1. 先搞懂华为OD机考和这道题的“场外信息”1.1 双机位机考到底怎么考华为OD的机考一般是远程在线评测用的是牛客网之类的平台考试全程开摄像头。“双机位”的意思是除了电脑摄像头对着你的正脸还要用手机或平板架一个副机位放在你的侧后方45度左右让监考画面能同时拍到你的电脑屏幕、双手和桌面。这种设计主要是为了防止代考、搜题这些作弊行为所以它的严格程度不亚于线下考场。实际操作时有几个细节值得提前准备。第一副机位设备要提前充满电、关掉通知最好开飞行模式再用Wi-Fi不然考试中突然弹电话进来轻则提醒重则判定异常。第二机位角度要提前拿胶带或手机支架固定好不要放在会晃的椅子上因为监考系统有随机抓拍如果画面里看不到手或者屏幕会被标记为可疑。第三电脑端建议用Chrome浏览器提前测好摄像头和麦克风权限有些考场还会要求你共享屏幕或开启页面录制。很多第一次考的朋友容易忽略的是环境检查。房间光线不能太暗背后不要有容易让人误解的东西桌上不要放纸质资料、手机、耳机尤其是无线耳机被拍到基本就是警告一次。我个人的建议是提前半小时进入考试链接把所有硬件过一遍再在草稿纸上写好常用的输入输出模板等倒计时结束直接开写。1.2 C卷、双机位和“最佳升级时间窗”的关系华为OD机考一般分成A、B、C、D等不同卷不同批次的考生拿到的卷子不一样但题型和考点是稳的。C卷作为一个常见批次题目风格偏应用题喜欢把堆排序、贪心、滑动窗口、动态规划这些经典算法包装成“业务升级”“任务调度”“资源分配”的场景。这道“最佳升级时间窗”就是典型代表。网上搜这道题会发现还有相似的名字比如“最优升级窗口”“最大可用升级时长”核心考点都指向区间扫描、差分数组、前缀和这一整套思路。题目的大致描述是这样的系统有N个升级任务每个任务有一个开始时间和结束时间任务在时间段内会持续占用系统资源同一时刻最多只能并行K个任务。现在要你找一个连续的升级时间窗口让这个窗口内任意时刻并行任务数都不超过K求满足条件的最长窗口长度以及对应的最早左端点。如果不能找到任何长度为1的合法窗口就输出0和-1。这道题之所以适合拿来当例题是因为它没有特别难的算法但非常考验对边界条件的处理。如果你能白板写出这道题的Java解法那么很多区间类变体题你都能顺下来。2. 题目建模从业务描述到算法问题2.1 抽象成数学模型先别急着写代码把题面翻译成数学语言。每个任务是一个闭区间[start, end]表示这个任务从 start 时刻开始到 end 时刻为止包括端点时刻一直在占用资源。系统同一时刻最多只能有 K 个任务在跑。我们要找一个连续时间段[L, R]使得在 L 和 R 之间的每一个整数时刻 t处于运行状态的任务数量都不超过 K。目标是让 R - L 1 最大如果有多个等长结果选择 L 最小的。这里最大的坑是边界处理。闭区间意味着在 start 时刻任务加入在 end 时刻任务还在运行要到 end 1 时刻才释放资源。很多人写差分数组时习惯在end处 -1结果边界一算就错。记住一句话开始时间加一结束时间的下一个时刻减一也就是用diff[start] 1和diff[end 1] - 1来记录变化量。为什么这样处理因为我们要统计的是“任意时刻”的并行任务数。假设一个任务为[2,3]它在时刻2和时刻3都运行。如果我们在diff[3] - 1那么时刻3的并行数就少算了这个任务。改成diff[4] - 1之后时刻3仍然算任务在运行到了时刻4才释放逻辑才对得上。2.2 核心算法选择差分数组 扫描线这类问题最直接的做法是差分数组和前缀和。如果时间范围很小比如1 t 10^6直接开一个等长的数组在每个任务的开始位置 1结束位置的后一位 -1然后从左到右累加就能得到每个时刻的并行任务数。但OD机考的数据范围通常很大时间点可能到10^9不可能开这么大的数组所以必须离散化。离散化的思想是我们并不关心每一个整数时刻的并行数只关心“变化点”。任务的开始和结束是变化点在这些点之间并行任务数是固定不变的。所以只需要把所有开始时间和结束时间的后一位收集起来排序然后扫描相邻两个变化点之间的区间段看这一段里的并行数是否小于等于K。这样做的好处是复杂度从 O(时间范围) 降到了 O(N log N)其中 N 是任务数量。排序 一次扫描就能解决空间复杂度 O(N)。这个方案在面对大范围输入时非常稳。2.3 为什么不用贪心、二分、线段树有些朋友看到“最长窗口”就想着二分答案或者用滑动窗口优先队列。当然这些思路在某些变体题里也能用但对这道题来说是杀鸡用牛刀。二分答案虽然可以但你还需要一个 check 函数去验证某个长度是否可行而且验证过程本质上还是要做区间覆盖统计复杂度不会比扫描线更优。线段树可以做区间最大值查询但需要动态维护区间加法代码量大考试时间那么紧张没必要自找麻烦。扫描线的直观理解是把每个任务看成往时间轴上放一个“覆盖区间”并行任务数就是每个点被多少个区间覆盖。我们要找的是一段连续没有被超过K个区间覆盖的区域。把这套逻辑想清楚代码写起来非常快也容易调试。3. Java实现完整代码和逐步解析3.1 数据结构设计我用的核心数据结构是HashMapInteger, Integer来存储差分变化量键是时间点值是该时间点的变化量。之所以用 Map 而不是数组是因为时间点可能很大很稀疏。然后取出所有 key 排序得到一个有序的时间点列表。还需要几个变量记录状态cur当前扫描到的区间段的并行任务数。segmentStart当前合法窗口段的起始时间。bestLen和bestStart目前找到的最优窗口长度和左端点。segmentStart的更新逻辑是这道题的精髓。当某一整段区间并行数大于K时说明当前窗口在这里断开了下一个合法段的起点应该从下一段变化点开始。当并行数小于等于K时当前窗口可以继续延长实时更新最优值。3.2 完整Java代码下面给出一个可以直接运行的版本输入格式为第一行两个整数 N 和 K接下来 N 行每行两个整数表示任务的开始和结束时间。import java.util.*; public class BestUpgradeWindow { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); MapInteger, Integer diff new HashMap(); int minT Integer.MAX_VALUE; int maxT Integer.MIN_VALUE; for (int i 0; i n; i) { int start sc.nextInt(); int end sc.nextInt(); minT Math.min(minT, start); maxT Math.max(maxT, end); diff.put(start, diff.getOrDefault(start, 0) 1); diff.put(end 1, diff.getOrDefault(end 1, 0) - 1); } if (n 0) { System.out.println(0 -1); return; } ListInteger times new ArrayList(diff.keySet()); Collections.sort(times); int cur 0; int bestLen 0; int bestStart -1; int segmentStart minT; for (int i 0; i times.size(); i) { int t times.get(i); cur diff.get(t); if (i 1 times.size()) { int nextT times.get(i 1); int segLen nextT - t; if (cur k) { int len nextT - segmentStart; if (len bestLen || (len bestLen segmentStart bestStart)) { bestLen len; bestStart segmentStart; } } else { segmentStart nextT; } } } if (bestLen 0) { System.out.println(0 -1); } else { System.out.println(bestLen bestStart); } } }3.3 关键逻辑逐段解释第一段是读入和差分的构建。end 1是关键前面已经解释过了这里再强调一遍任务在end时刻仍然占用资源所以释放时间必须是end 1。这样在扫描的时候区间[end, end1)覆盖数还是包含这个任务的。然后是排序。Map 的 key 集合是无序的必须排序后才能保证从左到右扫描时间轴。排序后的times列表中相邻的两个时间点t和nextT之间是“一整段连续时间”在这段区间内的任意整数时刻并行任务数都等于应用了t点变化量之后的cur。再来看状态更新。如果当前段cur K说明从segmentStart到nextT - 1之间都是合法的窗口长度是nextT - segmentStart。注意这里不用加1因为窗口区间是左闭右开的理解方式实际覆盖到nextT - 1长度刚好是nextT - segmentStart。如果当前段cur K说明这一段非法窗口在这里断裂segmentStart要从下一段的起始点重新开始。最后输出时如果bestLen仍然是0说明没有任何合法窗口按题目要求输出0 -1。否则输出长度和最早左端点。这里处理了多个等长窗口取最小左端点的情况只有当前长度大于最优长度或者等于最优长度但左端点更小的时候才更新。3.4 用示例验证代码看一个最简单的例子。输入3 1 1 3 2 4 5 6任务是三个区间[1,3]、[2,4]、[5,6]最多允许并行1个。手推一下1到2之间只有任务1合法2到4之间有两个任务重叠非法5到6之间只有任务3合法。所以最长合法窗口长度为2对应窗口[1,2]和[5,6]最早左端点是1。用代码跑一遍diff 中1:1, 4:-1, 2:1, 5:-1, 5:1, 7:-1排序后时间是[1,2,4,5,7]。扫描到[1,2)时 cur1合法窗口长度1[2,4)时 cur2非法重置[4,5)时 cur1合法但此时段长为1窗口变成4到4[5,7)时 cur2? 等等这里要仔细算。在时间点5有 -1 和 1 两个变化合并后净变化是0所以 cur在4之后是1到5点再加上0还是1实际[5,7)段 cur1长度是7-43看起来不对。让我重新整理 diff任务1[1,3]1:1, 4:-1任务2[2,4]2:1, 5:-1任务3[5,6]5:1, 7:-1。合并1:1,2:1,4:-1,5:0,7:-1。排序 key1,2,4,5,7。i0, t1, cur1, 区间[1,2)合法len2-11best(1,1)i1, t2, cur2, 区间[2,4)非法segmentStart4i2, t4, cur1, 区间[4,5)合法len5-41bestLen同样为1但 segmentStart4 bestStart1不更新i3, t5, cur1 (因为 diff[5]0cur不变), 区间[5,7)长度为2len7-43bestLen3bestStart4这里有问题了窗口 [4,6] 真的合法吗时间段4到5之间只有任务3等等任务2是 [2,4]在时刻4仍在运行任务3是 [5,6]在时刻5开始。区间 [4,5) 覆盖任务2[5,7) 覆盖任务3。这两个区间合并成 [4,7) 的话其实 [4,5) 覆盖任务2并行数为1[5,6] 覆盖任务3并行数为1两个任务没有重叠所以整个 [4,6] 确实合法。长度34,5,6三个时刻正确。但最早最优窗口实际上是 [1,2] 长度1不是最优。输出3 4符合手推吗手推最长窗口确实应该是 [4,6]长度3。所以输出正确。我先前手推时漏了任务2在时刻4的占用和任务3从5开始实际上4到6之间一直是合法的。这个例子很好地证明了代码的正确性也提醒我们手推时要仔细处理端点。再验证一个更复杂的场景。输入2 1 1 2 2 3任务1[1,2]任务2[2,3]并行上限1。时刻1只有任务1时刻2两个任务都运行并行数2时刻3只有任务2。所以合法窗口是 [1,1] 和 [3,3]长度均为1最早左端点1。代码输出应该为1 1。注意这里意味着时刻2不是一个合法点窗口不能跨过它。这个例子再次说明任务在 start 和 end 时刻都占用资源所以[1,2]和[2,3]在时刻2重叠。很多人把这个搞错以为两个相邻区间不重叠但实际上闭区间在端点处重叠了。4. 考场实战常见问题与避坑指南4.1 编译、输入输出和超时的坑在牛客网这种在线评测平台上Java 的主类名必须叫Main不能自定义成别的名字否则会因为找不到入口类直接编译失败。我自己就见过有人本地跑得好好的复制上去把类名改了结果白丢一道题的分。所以考前最好把模板背下来类名设置为Mainimport 该写的都写好Scanner 初始化放在第一行。输入读取方面数据量大的时候Scanner会比BufferedReader慢很多。OD机考有的题目用例非常大Scanner 连续读几万行有可能会超时。稳妥的做法是用BufferedReader按行读再split解析。不过如果平时用 Scanner 已经练得很熟可以先写 Scanner 版本万一测试发现超时再换至少思路是对的。还有一个常见的超时原因是 Map 的频繁自动装箱。Java 的HashMapInteger, Integer在 put 和 get 时会反复装箱拆箱数据量一大开销就很明显。如果真的被性能卡住可以考虑用两个数组手动写一个简单的离散化映射或者用TreeMap直接排序。在OD机考的难度下HashMap 通常够用但你要有这个意识。4.2 边界条件和极端用例这道题最容易被卡死的边界条件有三个。第一个是空输入或者 N0。如果没有任何任务按理说任何窗口都合法但最长窗口没有意义。我的处理是直接输出0 -1这个约定最好在解题时先想清楚避免运行时出现空集合异常。第二个是 end 1 溢出。如果题目给的时间范围是10^9级别end 1还在 int 范围内。但如果时间上限是2^31 - 1那么end 1就会溢出变成负数。稳妥的做法是全部用 long 类型处理时间点或者在读入时判断如果 end 已经是 int 最大值就不做 1而是使用一个更大的标记值。OD机考一般不会卡这个但养成用 long 的习惯能少踩很多坑。第三个是窗口跨越时间长段的情况。比如只有一个任务[1000000000, 1000000000]K1那么合法窗口就是这个单点长度为1。用差分数组扫描时diff 只有两个 key1000000000 和 1000000001扫描区间长度是1输出正确。但如果任务时间是[1, 1000000000]K1那么窗口长度就是 10^9int 范围内也够但如果你中间用了某个累加变量去数每个时刻那肯定会超时。4.3 调试技巧先手推样例再构造极端数据考场上的调试时间非常有限我建议每写完一版代码先用题目给的样例跑通再自己构造三个小用例全都不重叠的任务比如 [1,2]、[3,4]、[5,6]K1看最长窗口是不是 6。全部重叠的任务比如 [1,10]、[2,9]、[3,8]K1看最长窗口是不是1。单个任务验证边界闭区间逻辑。这三个用例能覆盖90%的边界错误。如果本地IDE支持断点调试记得在cur diff.get(t)那一行打一个条件断点观察 cur 超过K时是否正确地断开了段。很多时候不是思路错是segmentStart更新的位置不对导致窗口被错误地延长或缩短。我在写这道题的时候就因为在cur K和cur K两个分支里少更新了一次 len导致最后一个合法段没有被统计进去。这种问题靠肉眼很难发现但构造一个“最后一个任务单独在一段”的样例立刻就能暴露。5. 从这道题延伸出去的刷题策略5.1 相关题型和知识点串联学会这道题不只是会了一个题而是掌握了一类问题的通用解法。差分数组 扫描线这个组合在OD机考中非常高频常见的变体有求最大重叠区间数量、求最少会议室数量、求最多同时在线人数、求最佳活动安排时间等。它们本质都是把区间映射到时间轴上然后统计每个时刻的覆盖数。再往深一层如果题目要求“窗口内不能有任何时刻超过K”那其实就是这道题。如果题目改成“窗口内总工作量不超过K”那就是前缀和 二分。如果改成“最多可以取消一个任务的情况下求最长窗口”那就要加一层状态变成带容错的滑动窗口。我建议用思维导图把这几类放在一起对比练习的时候每做完一道题就想想它和“最佳升级时间窗”有什么异同。还有一类和“货物调度”“列车调度”相关的题目也是OD机考里的熟面孔它们的核心基本上就是区间分组问题每个区间需要一台设备求最少需要多少台设备。这类题可以直接用优先队列做也可以用差分数组算最大重叠数其实和这道题反过来理解就行。5.2 刷题时间和方法建议很多人在网上问“华为OD算法题刷多久能过”我的体感是如果每天能保证两到三小时的有效刷题坚持三到四周大部分C卷的算法题都能应付。重点不是刷题数量而是把每种算法模型的代码模板背熟。比如差分数组的模板滑动窗口的模板并查集的模板Dijkstra的模板都整理成自己的固定写法考试时直接套。刷题时不要只AC了就扔至少要做三件事第一看题解里有没有比你的代码更简洁的写法第二想一想如果把数据范围扩大十倍你的代码会不会超时第三把这道题整理进你的题型分类笔记。我当时整理区间类问题时就把“最佳升级时间窗”和会议室、发车调度放在一起后来遇到类似的题基本一眼就能识别出来。5.3 一个小小的实战心得最后分享一个我在实际机考中验证过的小技巧。正式考试时不要一上来就写最优解而是先花五分钟在草稿纸上把差分数组的示意图画出来。画出时间轴标出每个任务的开始和结束位置然后模拟一遍并行数的变化。这个动作看起来浪费时间实际上能帮你确认闭区间处理的细节避免很多边界错误。另外如果你在考场上一时想不起这个题的完整解法可以先写一个暴力版本保底。暴力做法是枚举每一个可能的窗口起点和终点每次重新统计区间内所有时刻的并行数。虽然会超时但至少能拿一部分用例的分。OD机考通常有多个测试点暴力能过几个算几个比交白卷好太多。在暴力版本通过后再往差分数组扫描线上优化心理压力会小很多。