GPU credit ledger with out-of-order events

Build an in-memory ledger for GPU credits. Credit arrives as grants: each one has a unique id, an amount, and a time window in which it can be spent. Grants may overlap in time.

Events reach the ledger over a network, so they can arrive in any timestamp order. A charge stamped at time 20 may show up after a charge stamped at time 50, and a grant can show up after charges that happen inside its window. Every answer must be the same as if all known events had been processed in timestamp order.

Implement a class CreditSystem:

• CreditSystem(): creates an empty ledger.
• add_credit(grant_id: str, amount: int, start: int, end: int) -> None: records a grant of amount credits, usable at any time t with start <= t < end.
• subtract(amount: int, timestamp: int) -> bool: records a charge of amount credits at timestamp. A charge spends from the usable grant that expires soonest first, then the next one. A charge is all-or-nothing. If the ledger can't cover it, or accepting it would leave an already accepted charge uncovered, return False and change nothing. Otherwise return True.
• get_balance(timestamp: int) -> int: returns the credits usable at timestamp, counting only charges stamped at or before timestamp.

Rules and constraints:

• Amounts are positive integers. Grant ids are unique. Timestamps are integers.
• At the same timestamp, a grant that starts then is usable, a grant that ends then is not, and charges apply in the order they arrived.
• Up to 10^4 calls in total.

Example 1

add_credit("a", 10, 0, 100)
add_credit("b", 5, 10, 40)
get_balance(20)      -> 15
subtract(7, 30)      -> True    # 5 from b (expires first), 2 from a
get_balance(25)      -> 15      # the charge at 30 hasn't happened yet
get_balance(30)      -> 8
get_balance(100)     -> 0       # a has expired

Example 2 (out of order)

add_credit("a", 10, 0, 100)
subtract(8, 50)      -> True
subtract(5, 20)      -> False   # would leave only 5 for the charge at 50
subtract(2, 20)      -> True
get_balance(60)      -> 0

Follow-up: most events arrive nearly in order. How do you avoid reprocessing the whole history on every call?