华为OD机考的C卷里有一类题把业务包装得很像运维排期一批服务器要在指定时间段内升级每台服务器有自己允许操作的时间窗题目问哪个时间段“叠”起来的服务器最多。我第一次看到“最佳升级时间窗”这个标题时第一反应是写成模拟排程的贪心题直到手算样例才发现它就是一道很经典的区间最大重叠问题。这篇文章把它用 Java、Python、JS、Go、C、C 六个版本完整过一遍重点讲清楚事件拆分、排序策略和输出边界。适合两类人一是准备华为OD C卷机考想在扫描线这类题上把代码写稳的人二是日常要处理会议室排期、值班表、运维窗口这类区间聚合需求的人。先把题读懂再看实现最后我会专门聊一聊双机位环境下怎么限时拿分。1. 题目原文复述先理解“最佳升级时间窗”到底在问什么1.1 按考场流传版本整理的题面我按自己在 C 卷见到的版本把题目还原成下面这个样子某个系统有 N 台服务器需要升级第 i 台服务器有一个可升级时间窗[s_i, e_i]表示服务器在这一段连续时间内处于可操作状态端点包含。现在要选一个连续的“最佳升级时间窗”使得这个时间段内处于可升级状态的服务器数量最多。如果有多个时间窗覆盖数量并列第一输出最早的那个输出内容包含最大覆盖数和这个时间窗的起止时间。输入的第一行是 N随后 N 行每行两个整数s_i、e_i。N 的范围一般到10^5时间戳可以是正负的大整数不一定落在小范围内。时间是整数粒度闭区间。面试场景里这道题包装成“服务器升级”但如果你把“服务器”替换成“会议”“预约”“在线用户时间段”它完全等价于另一道经典题给定若干区间求被覆盖次数最多的子区间。C 卷这种“换壳题”非常多题目包装越贴近业务越不要被描述带偏核心解法往往就藏在样例里。1.2 输入输出样例4 1 4 2 5 3 9 7 10对应输出3 3 4解释一下三个时间窗[1,4]、[2,5]、[3,9]在3到4这一小段内同时有效所以最多能覆盖 3 台服务器。时间窗[7,10]单独算一段覆盖数只有 1不是最优解。这里必须注意题目说的是连续整数时间段“3 到 4”不是“从 3 到 5”。原因是时间窗[1,4]在 5 这个整数点已经结束[2,5]在 6 结束[3,9]在 10 结束。三个窗口在 5 之前都还开着所以重叠段是[3,5)对应整数点3和4。1.3 为什么这题考的是扫描线而不是排序贪心很多人上手会想把所有时间窗按开始时间排序然后维护一个结束时间类似区间调度。但区间调度求的是“最多能安排几个不冲突的窗口”这里求的是“哪个时间段同时存在的窗口最多”这是两个完全不同的目标。区间调度要优先安排结束早的窗口贪心成立。而最大重叠窗口要求对每个被区间覆盖的点做“覆盖数统计”必然要处理每个窗口的开始和结束两个边界。把所有边界放到一条时间轴上观察覆盖数怎么起伏这就是扫描线思维。所以这道题的最优解法是把每个窗口拆成两个“事件”开始事件让覆盖数 1结束事件让覆盖数 -1排序后沿时间轴扫描一遍就能同时求出全局最大覆盖数和对应的最长时间段。复杂度 O(N log N)主要花在排序上。2. 核心算法差分事件扫描线为什么这个解法是标准的2.1 把每个窗口拆成“进场”和“离场”两个事件用生活化的方式理解就是一个场馆里每个窗口代表一个人开始时间是他进场结束时间是他离场。我们现在要知道哪个时间段场馆里人最多最简单的方法就是在门口记录进一个人计数 1走一个人计数 -1计数最大的那段时间就是“人最多的时间段”。对应到代码中每个窗口[s, e]生成两个事件在s位置产生一个1事件表示从这个点开始这个窗口参与覆盖计数在e 1位置产生一个-1事件表示过了e这个点之后它不再参与覆盖计数。为什么要用e 1而不是e这是整道题最容易错的地方。题目给的是闭区间[1,4]包含 4 这个整数点。假如在 4 直接做 -1扫描到 5 时计数已经减掉那么区间[1,4]对整数点 4 的覆盖就被砍断了输出会差一个点。用e 1做离场事件能保证“4 的覆盖有效5 开始覆盖失效”正好和闭区间的语义对齐。2.2 事件排序的细节同一坐标上先加后减把所有事件放进一个数组后需要排序。排序规则是先按坐标从小到大排坐标相同时1事件排在-1事件前面。这个规则很关键。同一个坐标点上可能同时存在“某个窗口的离场”和“另一个窗口的进场”比如[1,2]的离场点在 3[3,5]的进场点也在 3。这时候我们要保证同一坐标上的变化先叠加完再进入下一段去统计否则扫描过程中会出现“场地里人数瞬间跳动”的错误中间态。好在这种排序不会影响最终覆盖数因为同一点上的 1 和 -1 最终还是会互相抵消。但为了程序稳定、输出一致最好在所有语言里都统一写成“坐标升序、delta 降序”也就是 1 在前-1 在后。2.3 扫描时如何维护“当前覆盖数”和“最佳窗口”扫描过程不复杂但很多人会在“先更新还是先累加”上绕晕。正确做法是维护一个cur表示当前覆盖数维护一个prev表示上一个事件坐标每遇到一个新事件坐标x先检查[prev, x)这一段在这段区间里cur保持不变判断cur是否超过历史最大值如果超过或者并列但长度更长就更新最佳窗口[prev, x)更新完再把当前事件的增量加到cur上并把prev设为x。这里我用半开区间[prev, x)作为扫描单位输出时把右端点减 1变成闭区间[prev, x-1]。因为所有事件都发生在整数坐标上两个相邻事件坐标之间的覆盖数恒定窗口长度等于x - prev。用样例的四个窗口来走一遍窗口[1,4]、[2,5]、[3,9]、[7,10]拆成事件后坐标分别是11、21、31、5-1、6-1、71、10-1、11-1。扫描到 2 时cur 1段[1,2)覆盖 1扫描到 3 时cur 2段[2,3)覆盖 2扫描到 5 时cur 3段[3,5)覆盖 3这里更新最大覆盖数后面 5、6 两个离场点让cur掉回 17 进场后又变成 2但再也没有超过 3。所以答案是覆盖数 3时间段[3,5)输出闭区间就是3 4。这个算法时间复杂度 O(N log N)空间复杂度 O(N)对 N10^5 完全够用。如果时间戳范围很小还可以用差分数组但题目给的是大整数范围直接开数组一定会爆内存所以必须走事件排序。3. 六语言实现与细节差异这一章的代码全部按同一个逻辑实现事件数组 排序 单趟扫描。我会在每个语言小节里点出最值得注意的坑因为同一个逻辑在不同语言里的“写法成本”完全不一样。3.1 Java 实现重点是排序比较器华为 OD 机考如果选 Java类名通常要求写成Main包名不能有。下面这段可以直接作为完整答案提交。import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); long[][] events new long[2 * n][2]; int idx 0; for (int i 0; i n; i) { long s in.nextLong(); long e in.nextLong(); events[idx][0] s; events[idx][1] 1; events[idx][0] e 1; events[idx][1] -1; } Arrays.sort(events, (a, b) - { if (a[0] ! b[0]) { return Long.compare(a[0], b[0]); } return Long.compare(b[1], a[1]); }); long best -1; long bestL 0; long bestR 0; long cur 0; long prev events[0][0]; for (long[] ev : events) { long x ev[0]; if (x prev) { if (cur best || (cur best x - prev bestR - bestL)) { best cur; bestL prev; bestR x; } } cur ev[1]; prev x; } System.out.println(best); System.out.println(bestL (bestR - 1)); } }这里有三点必须说明第一事件数组用一个 2×N 的二维long数组不要用Integer做减法排序。坐标可能到10^9级别e 1一不小心就会超出int的范围我用long是为了彻底避开溢出问题。第二Comparable 里判断坐标是否相同时用a[0] ! b[0]不能用a[0] - b[0]。两个 long 相减仍然可能溢出而且long类型直接减法在极端正负值时不可靠Long.compare才是全量安全的。第三扫描循环里先检查[prev, x)再累加 delta 的顺序是刻意设计的。如果反着来会把当前坐标上的事件提前混入上一段导致覆盖数统计偏大或偏小边界用例直接翻车。3.2 Python最容易写但输入解析要快Python 版的核心逻辑和 Java 完全一致但代码可以短不少。唯一需要留神的是超大输入时的读取方式不要用input()一行行读直接sys.stdin.buffer.read()一把梭更快。import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) if not data: return n data[0] events [] p 1 for _ in range(n): s data[p] e data[p 1] p 2 events.append((s, 1)) events.append((e 1, -1)) # 坐标升序同一坐标 1 在前 events.sort(keylambda v: (v[0], -v[1])) best -1 best_l 0 best_r 0 cur 0 prev events[0][0] for x, delta in events: if x prev: if cur best or (cur best and x - prev best_r - best_l): best cur best_l prev best_r x cur delta prev x print(best) print(best_l, best_r - 1) if __name__ __main__: main()Python 的元组排序天然支持“先按第一个元素、再按第二个元素”所以(v[0], -v[1])这一行就完成了 Java 里需要手写比较器的工作。同一个坐标上1的 delta 是 1-1的 delta 是 -1取负后-1变成 -1、-1变成 1排序时 -1 排在 1 前面也就是 delta 大的先排刚好满足 1 优先的要求。Python 版本适合快速验证思路但如果你目标是机考拿满分一定要自己手动跑一遍样例并且注意best_r - 1的输出逻辑别把开区间直接当成闭区间打出去。3.3 JavaScript 和 Go读入和排序的细节差异JS 在牛客这类平台一般走 Node 环境输入用fs.readFileSync(/dev/stdin)读取。事件可以存成二维数组排序回调里需要显式返回差值。const fs require(fs); const input fs.readFileSync(/dev/stdin, utf8).trim().split(/\s/).map(Number); let idx 0; const n input[idx]; const events []; for (let i 0; i n; i) { const s input[idx]; const e input[idx]; events.push([s, 1]); events.push([e 1, -1]); } events.sort((a, b) { if (a[0] ! b[0]) return a[0] - b[0]; return b[1] - a[1]; }); let best -1; let bestL 0; let bestR 0; let cur 0; let prev events[0][0]; for (const [x, delta] of events) { if (x prev) { if (cur best || (cur best x - prev bestR - bestL)) { best cur; bestL prev; bestR x; } } cur delta; prev x; } console.log(best); console.log(bestL, bestR - 1);Go 版本要注意结构体排序的写法。Go 里没有内置的pair需要自己定义结构体然后用sort.Slice加比较函数。下面这一版用了int64存坐标输入解析用bufio.Scanner按单词读避免一次性加载整个文件到内存造成压力。package main import ( bufio fmt os sort strconv ) type event struct { x, delta int64 } func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Split(bufio.ScanWords) read : func() int64 { scanner.Scan() v, _ : strconv.ParseInt(scanner.Text(), 10, 64) return v } n : int(read()) events : make([]event, 0, 2*n) for i : 0; i n; i { s : read() e : read() events append(events, event{s, 1}, event{e 1, -1}) } sort.Slice(events, func(i, j int) bool { if events[i].x ! events[j].x { return events[i].x events[j].x } return events[i].delta events[j].delta }) best, bestL, bestR : int64(-1), int64(0), int64(0) cur, prev : int64(0), events[0].x for _, e : range events { if e.x prev { if cur best || (cur best e.x-prev bestR-bestL) { best, bestL, bestR cur, prev, e.x } } cur e.delta prev e.x } fmt.Println(best) fmt.Println(bestL, bestR-1) }Go 最容易踩的坑是scanner的默认缓冲区大小。如果输入行特别长建议在读完第一行后调大scanner.Buffer不过这道题按单词拆每个 token 都很短默认配置够用。3.4 C 与 C追求极致性能时的排序写法C 推荐用vectorpairlong long, int排序时写一个 lambda。注意比较器必须严格弱序不要写a.second b.second就完事要把坐标比较放前面。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairlong long, int events; events.reserve(2 * n); for (int i 0; i n; i) { long long s, e; cin s e; events.push_back({s, 1}); events.push_back({e 1, -1}); } sort(events.begin(), events.end(), [](const auto a, const auto b) { if (a.first ! b.first) return a.first b.first; return a.second b.second; }); long long best -1, bestL 0, bestR 0; long long cur 0; long long prev events[0].first; for (auto e : events) { long long x e.first; if (x prev) { if (cur best || (cur best x - prev bestR - bestL)) { best cur; bestL prev; bestR x; } } cur e.second; prev x; } cout best \n; cout bestL bestR - 1 \n; return 0; }C 语言没有现成的pair只能用结构体。qsort的比较函数必须返回严格全序当坐标不同时用pa-x pb-x ? -1 : 1不要用pa-x - pb-x作返回值因为 long long 相减可能溢出。另外记得手动malloc之后free虽然 OJ 通常不查内存泄漏但代码规范一些总没坏处。#include stdio.h #include stdlib.h typedef struct { long long x; int delta; } Event; int cmp(const void *a, const void *b) { Event *pa (Event *)a; Event *pb (Event *)b; if (pa-x ! pb-x) { return pa-x pb-x ? -1 : 1; } return pb-delta - pa-delta; } int main() { int n; if (scanf(%d, n) ! 1) return 0; Event *events (Event *)malloc(sizeof(Event) * 2 * n); int m 0; for (int i 0; i n; i) { long long s, e; scanf(%lld %lld, s, e); events[m] (Event){s, 1}; events[m] (Event){e 1, -1}; } qsort(events, m, sizeof(Event), cmp); long long best -1, bestL 0, bestR 0; long long cur 0; long long prev events[0].x; for (int i 0; i m; i) { long long x events[i].x; if (x prev) { if (cur best || (cur best x - prev bestR - bestL)) { best cur; bestL prev; bestR x; } } cur events[i].delta; prev x; } printf(%lld\n, best); printf(%lld %lld\n, bestL, bestR - 1); free(events); return 0; }C 版本里我最想提醒的一点是排序比较器不能有“相等歧义”。如果你只判断了pa-x pb-x就返回 0qsort对同坐标的 1/-1 顺序不做保证答案可能因为运行环境不同而变化。所以必须返回pb-delta - pa-delta让同坐标事件也有确定的先后顺序。3.5 六语言实现差异对比语言代码核心难点推荐使用场景Java比较器里用 Long.compare避免减法溢出机考最通用代码可读性最好Pythontuple sort 一行完成排序规则快速验证思路、写小样例JavaScriptNode 环境读入方式偏特殊熟悉前端的人应急选Go结构体排序需要手写比较逻辑对内存和并发要求高的本地工程Cvector lambda语法简洁性能高追求极限效率和稳定提交C手动管理内存qsort 比较器要小心练习底层能力考场上不建议首选六种语言实现同样的逻辑最终差异主要体现在两个地方一是排序写法二是输入输出模板。如果你考场只能选一门选你最熟的那门不要为了“六语言”这个标题真的现场写六遍。4. 边界条件与考场易错点4.1 区间开闭和端点重合最容易丢分的点闭区间的正确拆法我已经反复强调离场事件放在e 1。换到开区间语义时离场事件就放在e本身。考场上一旦发现样例能过但大数据 WA先检查是不是把[s,e]当成了[s,e)。还有一个更隐蔽的端点问题两个窗口在同一个整数点重叠比如[1,2]和[2,3]。如果你用“结束点在 e”的方式做差分会认为两个窗口在 2 这个点上瞬时切换不算重叠用e 1做差分就能正确识别出它们都覆盖整数点 2重叠数为 2。题目里的“连续时间段”到底怎么定义直接影响这一处的取舍考场上可以把样例和题面里的端点描述反复对照。4.2 多个最佳窗口时到底输出最早还是最长很多版本会问“最优升级时间窗”但“最优”的定义可能有两种并列时取最早出现或者并列时取最长。我的示例代码默认取“并列时最长”因为运维场景下同等覆盖数量时间段越长越好。如果你的题面要求取最早把更新条件里的长度比较改成if cur best or (cur best and prev best_l): ...一行改动就能切换。关键是写之前想清楚别等编程到一半再回头猜。4.3 时间戳范围和整数溢出题目里时间戳可能到10^9e 1之后就可能到10^9 1用int没问题但如果出题人把范围放到±10^9甚至更大int就会溢出。稳妥起见六种语言全部用 64 位整数存坐标。Java 的long、Go 的int64、C/C 的long long都是安全选择。Python 的整数天然不溢出可以放心。4.4 输入没有窗口的情况如果 N0事件数组为空扫描代码会直接越界。虽然机考大概率保证 N≥1但稳妥做法是在读入后判断一下空数组直接输出 0 或者按题目要求返回。这部分代码我省略了因为你一旦理解了循环原理自己补一行空判断也就十秒钟的事。4.5 所有窗口起点相同或终点相同当所有窗口起点都一样时排序后 1 事件会密集出现扫描过程会连续更新多次最佳窗口这一般没问题。但如果你把“最佳窗口”初始化成 0 而不是 -1就会出现“覆盖数为 0 的窗口”被误当成最优解的隐患。我代码里统一用best -1原因就在这里。它保证第一个合法事件段一定能进入更新分支而不是被初始化值挡住。5. 双机位考试环境下的实战策略5.1 双机位C卷读题和自测的节奏双机位意味着考试环境更严格不能切屏、不能查资料所有算法模板基本靠平时积累。进考场后我建议按这个节奏走先看输入输出样例手算一遍确认区间开闭语义用第一版代码直接写事件拆分 扫描不要先写暴力再优化因为这道题的暴力写多了容易把思维带偏自己造 3 组边界用例测试覆盖“首尾相接”“完全重叠”“无重叠”三类场景最后再检查输出格式尤其是整数和换行。这套流程大概 15 到 20 分钟。如果卡在某个用例上优先怀疑排序规则和输出右端点减 1这两处是最高频的 WA 原因。5.2 限时情况下选哪门语言提交最稳标题虽然列了六门语言但考场你只能交一版。如果你没有特别偏好的话我按稳定性排序Java 最稳语法死板但不容易写出隐晦 bugPython 写起来最快但大样例下运行时间会比 C 慢机考时间限制紧时要谨慎C 性能好前提是你对map、vector、lambda 都熟练Go、JS、C 属于“会哪门用哪门”不是不能用但模板细节更多临时换语言风险高。我自己最推荐 Java 或 Python。前者是大多数 OJ 的默认语言后者逻辑直观适合先快速验证正确性。5.3 最后一个小技巧把事件结构固定成模板这类“最大重叠区间”题不同平台换汤不换药。你可以把这套事件拆分逻辑固定成一个模板存在脑子里坐标不连续就用事件排序闭区间就把离场点放在 e1同坐标先加后减扫描时先统计旧段再应用新事件。只要记住这四句话遇到“最佳会议时间窗”“最多观众直播时段”“最大重叠值班区间”你都能在五分钟内写出正确的骨架代码。这也是我在多次机考和面试复盘里觉得最有复用价值的一点。这道题本身不复杂真正的难度从来不在算法而在题面翻译、边界语义和不同语言下的实现细节。把这三件事做扎实了C 卷里类似的扫描线题目基本都不会再丢分。