在 BFD 负载封顶分配器下二分搜索最小路由器数量

实现 solution(job_loads: list[int], load_cap: int) -> int。交易桌当前有 N = len(job_loads) 笔不可拆分的子单待路由,第 i 笔子单的整数负载成本为 job_loads[i](每笔订单线性累加到路由器的累计负载;源自 venue 连接器对该笔订单的资源估算),并且必须完整分配到某一台路由器(不允许跨路由器拆分)。所有路由器的累计负载上限相同,均为 load_cap。求**最小的整数 K(范围 [1, N])**,使得确定性的 best-fit-decreasing 分配器能把全部 N 笔订单装入 K 台路由器,且每台路由器的累计负载不超过 load_cap。该分配器由契约固定(下文给出),因此答案是「在该特定贪心策略下」可行的最小 K — 并非最优装箱意义下的最小 K。

分配器规则:把 job_loads 按降序排序;按该顺序处理每笔订单,放到当前累计负载最小且仍有 cap-room 的路由器(load_cap - current_load >= job);若所有已开路由器都没有 room,则新开一台路由器(消耗 K 预算中的一台);若 K 已开满且都没有 room,分配器失败。仅当存在某个 job_loads[i] 严格大于 load_cap 时才返回 -1 — 即便 K = N(每笔订单独占一台路由器),单台路由器也无法容纳超额负载。

关键的算法形态是对整数 K 在单调可行性谓词上做二分。定义 feasibility(K) 为 TRUE 当且仅当 BFD 分配器能把每笔订单装入 K 台路由器。由于分配器的决策只依赖当前已开路由器负载堆,不依赖 K 预算本身,多给一台路由器空闲槽只能让贪心至少不更差,即 feasibility(K+1) >= feasibility(K)。谓词在 [1, N] 上呈 FALSE-then-TRUE;对 K 二分搜索最小 TRUE。从 K = 1 到 N 顺序枚举 feasibility(K) 的朴素法在 N = 1500 时是 O(N^2 log N);二分省下一个 log N 因子,可在 2 秒内完成。

例

solution([10, 20, 30], 50) 返回 2。降序排列:[30, 20, 10]。当 K = 1 时,先把 30 放到 router-1(负载 30);处理 20 时,最空的 router-1 余量 50 - 30 = 20,装入,router-1 负载变 50;处理 10 时,router-1 余量 0,无路由器有空,K 预算已耗尽,分配失败。当 K = 2 时,前两步同前(router-1 负载到 50);第三步 router-1 没空,新开 router-2 负载 10,成功。所以 feasibility(1) 为 FALSE,feasibility(2) 为 TRUE — 最小 TRUE 的 K 等于 2。

同一组输入若 load_cap = 60,总负载等于 60,一台路由器即可装下,故 solution([10, 20, 30], 60) 返回 1;若 load_cap = 25,30 这笔已超过上限,solution([10, 20, 30], 25) 直接返回 -1,无需启动二分。

请参考 stubs/stub.py 的函数骨架。

实践背景

这是一个路由器容量规划工具:已知交易桌排队中的子单工作量(每笔子单携带一个由 venue 连接器估算出的整数负载成本 — token-bucket 成本、消息速率预算或类似的不可拆分的逐笔资源消耗指标),以及 venue 会话强制的单台路由器累计负载上限,desk 需要知道至少要预热多少台路由器,才能让 OMS 内置的确定性负载均衡器把队列中每一笔订单都成功落位、不让任何一台 session 溢出。「确定性贪心」是关键约束:生产系统不会在排单时跑离线装箱优化,而是直接调用 OMS 内置的固定 BFD 风格分配器,因此真正要回答的问题是「在这个分配器下,最少多少台路由器能跑完」而非「最优装箱解是几」。二分的形态使 N 达到 1500 笔子单时仍能在 O(N log^2 N) 内给出答案。-1 哨兵刻画的是无法靠扩容修复的退化情形 — 某笔子单的单笔负载已经超过了 venue 会话能承受的上限,无论开多少路由器它都不可能落位 — 这种情形被分配器捕获后回送为告警,而不是在分配器内部抛异常崩溃。本题与基于时间区间(并发重叠)驱动并发数的路由器排程类问题有本质区别:这里的形态是基于负载累加的装箱问题,绑定 cap 的量是累计负载本身,而非区间重叠。