题目重点：grant、subtract和查询时刻可乱序，需要重算与事件版本一致的余额。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练grant为[start,expire)有效，expire绝对时刻；同时间grant先于subtract，subtract按调用顺序。
- 按最早expire优先花；历史任一已到时刻的subtract不足则该查询None，未到的subtract不影响。无可用grant余额0。其他示例中的None口径/端点必须在面试澄清，不用它们推出本合同。
解题路线
- store只保存grant与charge事件，balance(t)收集时间≤t的事件排序重放，使用新状态，不修改原始记录。晚到早时grant可改变过去查询，所以余额结果依当前事件版本。
- 维护expiry最小堆及total；每事件前移除expire≤at余额，再处理grant或charge。charge先确认total足够，然后逐grant最早expiry扣，剩余非零放回堆。
- 同一查询不会重复花历史charge，因每次重放隔离；多次query必须幂等。优化可按时间索引和checkpoint，但新增更早事件要失效受影响checkpoint，不能只用墙钟顺序缓存。
手动走一遍
A4在[20,60)、B3在[30,40)，30扣2先花B，余额5；40时B余1过期，余额4。先记录30扣4，查询10按训练合同0；后加[20,35)的4可使30查询0。不同空值语义应明确，不能用未来失败污染10。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from heapq import heappush,heappop
class Credits:
def __init__(self):self.grants={};self.charges=[]
def add(self,key,amount,start,expire):
if key in self.grants or amount<0 or expire<=start:raise ValueError("unique grant, nonnegative amount, exclusive expiry")
self.grants[key]=(amount,start,expire)
def subtract(self,amount,time):
if amount<0:raise ValueError("nonnegative amount")
self.charges.append((time,len(self.charges),amount))
def balance(self,time):
events=[]
for sequence,(key,(amount,start,expire)) in enumerate(self.grants.items()):
if start<=time:events.append((start,0,sequence,amount,expire))
for at,sequence,amount in self.charges:
if at<=time:events.append((at,1,sequence,amount,None))
heap=[];total=0
for at,kind,sequence,amount,expire in sorted(events):
while heap and heap[0][0]<=at:total-=heappop(heap)[2]
if kind==0:heappush(heap,(expire,sequence,amount));total+=amount
else:
if total<amount:return None
total-=amount
while amount:
end,index,left=heappop(heap);used=min(amount,left);left-=used;amount-=used
if left:heappush(heap,(end,index,left))
while heap and heap[0][0]<=time:total-=heappop(heap)[2]
return total
复杂度
G grants/C charges，query事件排序O((G+C)log(G+C))，堆操作合计O((G+C)logG)，因为每charge至多一次部分重插、grant完全消耗最多G次；O(G+C)重放空间。
易错点与追问
容易失分的边界
- 将expire当duration会改变边界。
- charge按grant创建顺序扣，可能让快过期额度白白损失。
继续深挖
- 晚到事件如何失效历史快照且支持生产延迟预算？
- 是否拒绝不合法扣减并永久记拒绝决定，与重放None合同有何差别？
