池化资源共享题解：区间重叠最大值与差分数组、扫描线多语言实现

前段时间我在刷华为OD机考C卷的时候碰上一道叫“池化资源共享”的题双机位机考环境下有限时压力读题、建模、动手写代码基本是一气呵成的事。题目本身不绕但它把“资源池”这种并发场景抽象成区间问题再让你用 Java、Python、JS、C/C、Go 五种语言里的任意一种落地考察的东西其实很综合。网上问这题的人不少今天我把题面拆解、两套主流解法、五语言实现和一些容易踩的坑一起讲透。1. 题面解读池化资源共享到底在考什么1.1 我当时遇到的题目描述原题大致是这样的某个系统维护一个共享资源池系统会收到一批任务请求。每个任务用三个整数描述分别是 l、r、k表示该任务从时刻 l 开始持续占用 k 个单位资源到时刻 r 结束释放资源。现在给定所有任务要求计算系统在任意时刻同时被占用的资源总量最大值这个最大值就是资源池至少需要提供的容量。输入描述 第一行一个整数 M表示任务数量。 接下来 M 行每行三个整数 l、r、k。输出描述 一个整数表示资源池所需的最小容量。举个例子3 0 3 2 1 5 2 4 6 3我来手动推一下这段数据。任务 A 从 0 到 3 占 2 个资源任务 B 从 1 到 5 占 2 个资源任务 C 从 4 到 6 占 3 个资源。时刻 0 到 1 只有 A占用 2时刻 1 到 3 有 A 和 B占用 4时刻 3 到 4 只有 B占用 2时刻 4 到 5 有 B 和 C占用 5时刻 5 到 6 只有 C占用 3。所以峰值出现在时刻 4 到 5最大并发占用为 5答案就是 5。这道题本质上是一个经典区间问题的变体给定若干带权区间[l, r)每个区间有权重 k求这些区间在任意点上的权重覆盖总和最大值。它和你熟悉的“会议室预订”“最多有多少架飞机同时在飞”是同一类模型只是把所有区间的权重从 1 变成了 k多了个资源数量维度。1.2 为什么机考喜欢出这种题这类题在机考里出现频率很高原因很直接它考察的是面试者在真实系统里的资源管理理解能力。你在业务系统里天天遇到的各种池——数据库连接池、线程池、内存池、云环境的计算资源配额本质上都是一个有限容量池子承载不定数量请求的问题。数据库连接池容量设多少才够高峰期会不会因为连接数不够导致请求排队这些问题落到算法层面就是“区间重叠最大值”的计算。另外这道题在代码实现上有几个天然考点能否意识到区间是半开区间还是闭区间这直接影响边界处理。能否处理好“同一时刻既有任务结束又有任务开始”的顺序问题。能否根据数据范围选对算法不会一上来就写个双重循环。能否在语言层面处理大数溢出、排序稳定性、数组越界这些细节。一个看似简单的区间问题能同时考察建模能力和代码功底所以 OD 机考把它放进 C 卷我一点都不意外。2. 两套主流解法差分数组与事件扫描2.1 差分数组能直接开数组时最优雅差分数组是个很漂亮的技巧。它的核心思路是如果有一个原始数组 a它的差分数组 d 满足 d[i] a[i] - a[i-1]那么对原数组 a 的区间[l, r)做整体加 k等价于对 d[l] 加 k、对 d[r] 减 k。最后想要恢复 a 的每个位置值只需要对 d 做一次前缀和。放在这道题里思路就变成这样开一个长度足够覆盖所有时间点的大数组 diff初始全 0。对每个任务(l, r, k)执行diff[l] k; diff[r] - k;。从第 0 个时刻开始做前缀和累加过程中记录最大值这个最大值就是答案。为什么在 r 处减而不是 r 1这取决于区间定义。如果我们把区间定义为左闭右开[l, r)意味着任务在 r 时刻结束释放r 时刻本身不再占用资源。那么对 r 位置减 k 是正确的。如果定义为闭区间[l, r]则应该在 r 1 位置减 k因为 r 时刻还在占用。这里必须统一口径否则差一个边界就会出错。这种解法的优点是写法简单、常数小、不容易出错。缺点也很明显它要求时间点的范围不能太大。如果 l、r 的取值范围到了一亿这个级别直接开数组内存就爆了。时间复杂度 O(M T)T 是时间点取值范围空间复杂度 O(T)。2.2 离散化事件扫描时间跨度大时的主场当时间点跨度很大、但任务数量 M 相对不多时开大数组就不现实了。这时候把“变化点”提取出来排序处理就是标准的扫描线做法。具体步骤把每个任务拆成两个事件在 l 时刻发生“加 k”事件在 r 时刻发生“减 k”事件。把所有这些事件按照时间先后排序。顺序扫描事件列表维护一个当前占用 cur。遇到加事件就cur k遇到减事件就cur - k。每次更新 cur 后和全局最大值 ans 比较保留较大值。这里要注意一个细节同一时刻既有加事件又有减事件时先处理哪个如果我采用半开区间[l, r)那么 l 时刻任务开始占用资源r 时刻任务已经释放了。假设一个任务在 3 结束另一个任务在 3 开始实际上 3 时刻没有重叠正确结果应该是最大值不超过两者相加。但如果先处理加事件当前值会短暂地叠加导致误判。正确的顺序是同一时间点先处理所有减事件再处理加事件。这样能保证结束的任务先释放开始的任务再占用。我在写代码时习惯把减事件的时间稍微排前比如排序时如果时间相等把减事件放在加事件前面。如果你用的是差分数组方案则不存在这个问题因为差分数组天然把同一位置的加减合并了在同一个索引上先加后减还是先减后加前缀和恢复之后结果是一样的。这种方案的时间复杂度 O(M log M)瓶颈在排序。空间复杂度 O(M)。2.3 为什么不优先推荐优先队列很多同学一看到“区间重叠”就条件反射想到优先队列尤其是做过“会议室问题”之后。但在这里要分情况讨论。如果你遇到的是简化版每个任务只占 1 个单位资源也就是 k 恒等于 1让你求同时最大任务数那用小根堆维护结束时间确实很顺。按开始时间排序后遍历每个任务先把堆里所有结束时间小于等于当前开始时间的任务弹出再把当前任务结束时间压入堆堆的大小就是当前并发任务数取最大值即可。但原题里每个任务占用的资源数量 k 是任意的。这时候堆的方法麻烦一些你要按资源单元拆分或者额外维护多个结束时间队列代码变得冗长而且容易在处理释放顺序时出错。相比之下扫描线只需要维护一个 cur 数字加加减减就能解决无论是思维复杂度还是代码量都更低。所以我的建议是这道题优先掌握差分数组和事件扫描两种方法优先队列可以作为扩展思路了解一下但不是首选。3. 多语言落地五种语言写出同一道题3.1 Java用 long 数组避免溢出Java 在机考中出现频率最高。这道题我先给一个差分数组版本因为它最直观。核心代码大致这样import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); int maxTime 0; int[][] tasks new int[m][3]; for (int i 0; i m; i) { tasks[i][0] sc.nextInt(); tasks[i][1] sc.nextInt(); tasks[i][2] sc.nextInt(); maxTime Math.max(maxTime, tasks[i][1]); } long[] diff new long[maxTime 2]; for (int i 0; i m; i) { int l tasks[i][0]; int r tasks[i][1]; int k tasks[i][2]; diff[l] k; diff[r] - k; } long cur 0; long ans 0; for (int i 0; i maxTime; i) { cur diff[i]; ans Math.max(ans, cur); } System.out.println(ans); } }有几个点要提醒diff 数组类型要用 long。单个 k 可能不超过 int但多个 k 累加到同一个位置时完全可能超过 int 上限。Java 的 int 最大是 21 亿多资源量很可能顶穿这个数。数组长度建议开maxTime 2防止 r 恰好等于 maxTime 时diff[r] - k越界。扫描到 maxTime 即可diff 数组再往后的位置没必要扫。如果 maxTime 非常大比如 10 的 9 次方上述方案直接拜拜。这时候换成事件扫描import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); Listlong[] events new ArrayList(); for (int i 0; i m; i) { long l sc.nextLong(); long r sc.nextLong(); long k sc.nextLong(); events.add(new long[]{l, k, 1}); // 1 表示加 events.add(new long[]{r, k, 0}); // 0 表示减 } events.sort((a, b) - { if (a[0] ! b[0]) return Long.compare(a[0], b[0]); return Long.compare(a[2], b[2]); // 减事件排在加事件前面 }); long cur 0; long ans 0; for (long[] e : events) { if (e[2] 1) cur e[1]; else cur - e[1]; ans Math.max(ans, cur); } System.out.println(ans); } }这里我自定义排序时把“减事件”排在“加事件”前面用 0 和 1 标记类型。这个顺序非常重要我们后面还会详细说。3.2 Python字典模拟稀疏差分Python 写这类题非常舒服尤其是用字典模拟稀疏差分数组时不用预先知道时间范围。差分数组思路配合 dict 的写法import sys def main(): data sys.stdin.read().strip().split() if not data: return m int(data[0]) idx 1 diff {} for _ in range(m): l int(data[idx]); r int(data[idx 1]); k int(data[idx 2]) idx 3 diff[l] diff.get(l, 0) k diff[r] diff.get(r, 0) - k cur 0 ans 0 for t in sorted(diff.keys()): cur diff[t] if cur ans: ans cur print(ans) if __name__ __main__: main()这段代码看起来短但你得理解它和数组差分的一个区别数组差分的每个索引都在连续的内存空间里扫描时直接遍历索引即可不需要排序。但 dict 的 key 是稀疏的如果你用for t in sorted(diff.keys())本质上是把时间点取出来排序了复杂度变成了 O(M log M)。为什么还是可以这么写因为当时间范围很大、不适合开数组时dict 方案在时间和空间上都是平衡的它相当于把“离散化”隐含在字典里了。你不需要手动收集所有时间点、去重、排序字典天然只存出现过的变化点。Python 的一个常见坑是dict.get(l, 0)写漏默认值 0导致 KeyError这在机考环境下容易让人手忙脚乱。如果担心字典排序性能直接用列表存事件也可以代码差别不大但需要自定义排序规则。我的习惯是数据量在 10 万级别以内dict 方案足够稳数据量更大就改用列表事件 sort。3.3 JSMap 与排序的取舍JavaScript 在 LeetCode 风格的环境里用得很多机考也支持但 JS 写算法题有几个和 Java、Python 不太一样的习惯。差分数组方案function solve(input) { const lines input.trim().split(\n); const m parseInt(lines[0]); const diff new Map(); let maxTime 0; for (let i 1; i m; i) { const [l, r, k] lines[i].split( ).map(Number); diff.set(l, (diff.get(l) || 0) k); diff.set(r, (diff.get(r) || 0) - k); maxTime Math.max(maxTime, r); } let cur 0; let ans 0; for (let t 0; t maxTime; t) { if (diff.has(t)) { cur diff.get(t); ans Math.max(ans, cur); } } console.log(ans); }我在这里用了 Map 而不是普通对象原因是对象会把数字 key 转成字符串并且在遍历时会包含原型链上的属性容易出隐藏 bug。Map 则严格区分 key 类型性能也更好。上面代码扫描了 0 到 maxTime 的每个整数。如果时间跨度特别大这种扫描显然不行应该改成把 Map 的 key 取出来排序const times Array.from(diff.keys()).sort((a, b) a - b); let cur 0; let ans 0; for (const t of times) { cur diff.get(t); ans Math.max(ans, cur); } console.log(ans);JS 里还有一个很典型的坑Array.prototype.sort()默认按字符串排序而不是按数值排序。如果你不传比较函数[10, 9, 100]会被排成[10, 100, 9]结果全错。所以任何数值排序都必须显式传(a, b) a - b。3.4 C/Cvector 排序扫描注意 long longC 写这种题性能最好但要小心的细节也多。我给出事件扫描版本这也是 C 机考中最稳妥的写法。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m; cin m; vectorlong long time; vectorlong long delta; // 或者用一个 struct / pair 数组 vectorpairlong long, long long events; // first: 时间点, second: 变化量 vectorint type; for (int i 0; i m; i) { long long l, r, k; cin l r k; time.push_back(l); delta.push_back(k); time.push_back(r); delta.push_back(-k); } // 更清晰的做法把时间和变化量打包排序 vectortuplelong long, long long, int ev; // 时间, 变化量, 类型(0减,1加) for (int i 0; i m; i) { long long l, r, k; cin l r k; ev.emplace_back(r, -k, 0); ev.emplace_back(l, k, 1); } sort(ev.begin(), ev.end(), [](auto a, auto b){ if (get0(a) ! get0(b)) return get0(a) get0(b); return get2(a) get2(b); // 0 减排前面 }); long long cur 0; long long ans 0; for (auto e : ev) { cur get1(e); ans max(ans, cur); } cout ans \n; return 0; }上面这段代码我故意保留了两种写法雏形。实际比赛里别搞这么乱统一用结构体最清晰struct Event { long long t; long long delta; int type; // 0 减, 1 加 bool operator(const Event other) const { if (t ! other.t) return t other.t; return type other.type; } };C 需要注意的几点所有和资源量、总量相关的变量都用long long。int 在某些平台上只有 32 位累加很容易溢出。结构体排序如果你自己写operator注意排序规则要和“同时刻先减后加”一致。C 17 以后可以用结构化绑定for (auto [t, d, ty] : ev)代码更简洁但机考环境如果是较老的 GCC 版本可能不支持最稳妥还是直接用get或成员变量。输入量很大的时候cin默认会拖慢速度ios::sync_with_stdio(false); cin.tie(nullptr);这两行建议写上。3.5 Gosort.Slice 与正确性陷阱Go 写算法题越来越常见机考支持 Go 1.x 环境。Go 没有 C 那么复杂但也有一些独有的小坑。事件扫描的 Go 实现package main import ( bufio fmt os sort strconv strings ) type Event struct { t int64 delta int64 typ int } func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Scan() m, _ : strconv.Atoi(scanner.Text()) events : make([]Event, 0, 2*m) for i : 0; i m; i { scanner.Scan() parts : strings.Fields(scanner.Text()) l, _ : strconv.ParseInt(parts[0], 10, 64) r, _ : strconv.ParseInt(parts[1], 10, 64) k, _ : strconv.ParseInt(parts[2], 10, 64) events append(events, Event{t: r, delta: -k, typ: 0}) events append(events, Event{t: l, delta: k, typ: 1}) } sort.Slice(events, func(i, j int) bool { if events[i].t ! events[j].t { return events[i].t events[j].t } return events[i].typ events[j].typ }) var cur, ans int64 for _, e : range events { cur e.delta if cur ans { ans cur } } fmt.Println(ans) }Go 的坑主要在以下方面int类型在 32 位平台上是 32 位在 64 位平台上是 64 位。机考环境一般是 64 位但为了保险资源量这种可能很大的数我直接用int64。排序用sort.Slice比较器一定要自己写清楚。Go 默认没有对结构体 slice 的内置排序你必须提供比较函数。如果同时刻先减后加的规则没处理好同样会出错。我在构造 Event 时故意把减事件放前面、加事件放后面这样即使 sort 是稳定的也不会受到原本插入顺序干扰。但实际上 Go 的sort.Slice不是稳定排序所以这种依赖不太好正确做法仍然是显式在比较器里用 typ 区分。用bufio.Scanner读大数据时默认缓冲区 token 上限是 64K如果某行特别长会报错。可以调用scanner.Buffer(make([]byte, 1024*1024), 1024*1024)扩大缓冲区。4. 上机最容易踩的 5 个坑4.1 区间开闭半开区间是唯一解我重新强调一下这个问题。题目里的时间区间到底包不包含右端点是决定代码正确性的第一个关键选择。如果你读过不少面经会发现同一个问题不同版本的题面里区间的定义可能不同。有的写l 到 r 之间有的写l 到 r含 r。最安全、最利于编码的方式是把所有区间统一成[l, r)左闭右开任务从 l 开始占用到 r 结束释放。统一成半开区间后事件扫描和差分数组的边界都很好处理。差分数组里diff[l] k; diff[r] - k;的写法正是基于半开区间。如果题目明确说是闭区间你必须在 r 1 处减 k但我在面试题里看到的版本绝大多数是半开区间。审题时先用一个简单例子在草稿纸上验证你的开闭假设别直接埋头写代码。4.2 事件同刻排序先结束还是先开始这个前面反复提到了它是我见过出错率最高的细节。同一时刻有任务结束又有任务开始如果先处理开始事件当前占用值会瞬间多出刚释放的资源数导致答案偏大。比如一个任务0 2 5和一个任务2 4 3理想情况下 0 到 4 之间最大占用是 5因为第二个任务在 2 才开始第一个任务在 2 已经结束。但如果你在同一时刻先加后减第一次扫描到时刻 2 时会先加上 3cur 变成 8于是最大占用误算成 8。我的经验是减事件排在加事件前面。无论是自定义排序还是构造事件时用类型字段标记都要确保这一点。4.3 数据范围与溢出资源量 k 单个值可能不大但同一时间点多个任务的 k 累加起来就说不准了。差分数组和事件扫描都必须用 64 位整数Java 用 longPython 不用管整数无限大JS 用 Number 在超过 2 的 53 次方时会丢精度C 和 Go 用 long long / int64。另一个溢出点是时间点本身。如果 l、r 的取值范围接近 int 上限你的循环变量for (int t 0; t maxTime; t)可能因为 t 溢出而无限循环。所以时间点也建议用 64 位或者仔细评估范围。4.4 差分数组越界与内存差分数组方案里如果你把数组长度设成maxTime扫到maxTime时访问diff[r]就访问到diff[maxTime]这已经是最后一个有效下标勉强可以。但如果你在计算完所有任务后还要在maxTime 1的位置做收尾就可能越界。最保险的做法是数组长度开maxTime 2甚至更大一点。这个多出来的两个位置不浪费多少内存但能救你一次越界崩溃。另外如果 maxTime 是 10 的 7 次方开一个 long 数组就是 80 MB 内存很多机考环境会内存超限。这时候果断换事件扫描别硬撑。数据范围题面通常会给你先估算再选方案。4.5 输入输出的空格与多行机考平台对输出格式有严格要求只要多输出一个空格或换行都可能判Presentation Error。Java 的System.out.println输出后自带换行别在行尾额外拼一个空格。C 用\n而不是endlendl会强制刷新缓冲区数据量大时拖慢速度。Python 用sys.stdout.write(str(ans))或print(ans)都行但别在多个测试用例之间打印多余空行除非题目要求。如果题目明确有多组测试数据你就得处理“读入直到 EOF”的情况。C 用while (cin m)Java 用while (sc.hasNextInt())这要预先看题面约定。5. 测试用例与实战自查5.1 一组手工用例我在机考前会把下面这些用例存在本地提交前跑一遍自测用例1 1 0 10 5 期望输出5 用例2 3 0 3 2 1 5 2 4 6 3 期望输出5 用例3 2 0 2 5 2 4 3 期望输出5 用例4 4 1 4 3 2 5 2 4 7 1 6 8 4 期望输出6 用例5 2 0 1000000000 1000000000 0 1000000000 1000000000 期望输出2000000000用例 3 专门用来验证同一时刻先减后加的顺序。用例 5 用来验证大数处理两个任务重叠总占用是 20 亿用 int 正好溢出看你能不能输出正确答案。5.2 随机对拍给自己兜底如果你时间充裕我强烈建议写一个随机测试生成器和你自己最信任的暴力解法做对拍。暴力解法非常简单把所有时间点离散化后对每个区间遍历它覆盖的时间点累加 k最后取最大值。虽然时间复杂度高但正确性容易保证。生成随机的小数据跑几百组对比如果扫描线或差分数组的结果和暴力结果不一致你就知道边界哪里出问题了。我之前在练这道题的时候用 Python 写了个暴力版和差分版对拍很快就抓住了“同刻排序”这个细节。手动测试往往想不全面随机测试能覆盖到各种刁钻情况。6. 写在最后一点个人体会这类区间资源池的题我刚接触时也容易想复杂。后来发现只要抓住一个关键点剩下的推导都很顺把每个任务的开始和结束拆成事件用一条扫描线从左往右推维护当前并发量答案就是扫描过程中的最大值。这个思维模型几乎可以套用到所有资源池、会议室、航班并发这类题目上。实际机考时我一般会先看数据范围再决定用差分数组还是事件扫描。时间点在百万级以内就写差分时间点太大就写事件排序。每个语言我都写过一遍Java 和 C 更侧重 long 类型和排序规则Python 和 JS 更侧重字典/Map 的用法Go 则要注意 sort.Slice 比较器的写法。如果你把这五种解法都过一遍再遇到区间相关的变形题基本不会慌。最后再分享一个小技巧考试时边上放着纸笔先画一条时间轴把示例数据的占用情况画出来再对照代码走一遍很多边界问题就能提前暴露比写完再调试省时间得多。