← 返回编程题库
coding-greedy-fee-tier-coverage中等免费版2000ms未尝试

用最少手续费档位覆盖目标交易量区间

Minimum Fee-Tier Selection to Cover a Target Volume Range

开始编码

某流动性吃单台在一个支持「阶梯手续费叠加优惠」的交易场所执行订单:每个手续费档位是一段连续的成交量区间 [low, high),区间内享受一档固定(优惠)费率。为了让母单成交量落在 [Q_lo, Q_hi) 范围内的每一份累计成交量都享受到某档优惠,必须用一组连通的档位把整段范围完整覆盖——目标区间内的每一档累计成交量都必须落在至少一个被选中的档位里。开通每个档位都有一份固定的法务/运营成本,所以策略台希望用尽可能少的档位把目标区间覆盖完。

请实现 solution(target: list[int], tiers: list[list[int]]) -> int,其中 target = [Q_lo, Q_hi] 是要覆盖的左闭右开成交量区间,tiers 是若干 [low, high] 形式的左闭右开档位区间。返回完整覆盖 [Q_lo, Q_hi) 所需的最少档位数;若覆盖不可行则返回 -1。约定:Q_lo == Q_hi 时返回 0(空区间不需要档位,哪怕一个档位都没有);tiers 为空且目标非空时返回 -1;任何 low 严格大于当前覆盖前沿的档位都不能作为下一个选择(连通性要求)。

示例solution([0, 100], [[0, 40], [20, 60], [50, 90], [80, 100]]) 应返回 4。贪心扫一遍:在前沿 0 处只有 [0,40) 可用,推到 40;在 low ≤ 40 的候选里 reach 最远是 [20,60),推到 60;接下来 [50,90) 推到 90;最后 [80,100) 收尾。每一步都挑「可衔接的档位中 high 最大」的那一个。再看 solution([0, 100], [[0, 30], [40, 100]]) 返回 -1:覆盖到 30 后,剩下的档位 [40,100) 起点 40 > 30[30, 40) 这段无人能补,硬缺口。再看 solution([10, 30], [[10, 30]]) 返回 1,最简单的单档完整覆盖情形。

朴素地按 low 从小到大顺序选(「谁先到位选谁」)是错的——这只优化了档位上场的时间,没考虑上场后能推多远;可能选了一个早早可用但只多覆盖了一点点的档位,结果后面还得多用一档,而其实有一档可衔接、reach 更远的档位本可以一步到位。正确的不变量是在可衔接候选中挑 high 最大的:可以用经典的交换论证证明它最优——若另一个最优解在这一步选了 high 较小的档位,把它换成当前可选 high 最大的档位,后续每一个原本可用的档位仍然可用(因为前沿只会被推得更远),所以替换之后的解仍是合法解、长度不增加。算法本体就是排序后双指针线性扫,整体 O(n log n),主要开销在排序。

约束条件

  • 0 ≤ Q_lo ≤ Q_hi ≤ 10⁹
  • 0 ≤ len(tiers) ≤ 10⁴
  • 0 ≤ tier[low] ≤ tier[high] ≤ 10⁹
  • 若 `Q_lo == Q_hi`,目标为空区间,无论 `tiers` 是什么都返回 `0`
  • 若 `[Q_lo, Q_hi)` 内出现任何无法用现有档位填补的缺口,返回 `-1`
  • 档位是左闭右开区间 `[low, high)`——同一点上相接视为连通(不算缺口)

样例

Case 1 · single tier covers the whole target

输入: [[10,30],[[10,30]]]

期望: 1

唯一可用的档位 [10,30) 恰好覆盖目标区间 [10,30),只需 1 个档位。

Case 2 · four-tier chain covers wide target

输入: [[0,100],[[0,40],[20,60],[50,90],[80,100]]]

期望: 4

贪心从 0 出发:先选 [0,40)(reach=40);再在 low≤40 中挑 reach 最远的 [20,60)(reach=60);接着 [50,90)(reach=90);最后 [80,100)。共 4 个档位刚好封住区间,每一步都把指针推到该候选集中能到达的最远位置。

Case 3 · interior gap forces uncoverable

输入: [[0,100],[[0,30],[40,100]]]

期望: -1

覆盖到 30 后,在 low≤30 的候选里没有任何档位([40,100) 的 low=40 严格大于 30),出现硬缺口,无法继续推进,返回 -1。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · single tier covers the whole target

输入: [[10,30],[[10,30]]]

期望: 1

唯一可用的档位 [10,30) 恰好覆盖目标区间 [10,30),只需 1 个档位。

Case 2 · four-tier chain covers wide target

输入: [[0,100],[[0,40],[20,60],[50,90],[80,100]]]

期望: 4

贪心从 0 出发:先选 [0,40)(reach=40);再在 low≤40 中挑 reach 最远的 [20,60)(reach=60);接着 [50,90)(reach=90);最后 [80,100)。共 4 个档位刚好封住区间,每一步都把指针推到该候选集中能到达的最远位置。

Case 3 · interior gap forces uncoverable

输入: [[0,100],[[0,30],[40,100]]]

期望: -1

覆盖到 30 后,在 low≤30 的候选里没有任何档位([40,100) 的 low=40 严格大于 30),出现硬缺口,无法继续推进,返回 -1。