GPU Credits

Background. A team runs jobs on GPUs paid for with credits. Credits come in as grants and go out as charges, and each is recorded with the time it happened. Records reach the ledger in any time order: a grant dated 5 can be recorded after a charge dated 9.

Implement the class CreditLedger in ledger.py with three methods:

• grant(time, amount) records a grant of amount credits at time.
• charge(time, amount) records a charge of amount credits at time and returns True if it goes through, False if it is refused.
• balance_at(time) returns the credits left at time, an integer.

The ledger reads every recorded entry in time order, whatever order they were recorded in. At one time, grants come before charges, and entries of the same kind keep the order they were recorded in. Going through the entries in that order, a grant adds its amount, and a charge goes through if the credits left just before it cover its amount. Otherwise the charge is refused and takes nothing, not even part of its amount.

• balance_at(time) is what is left after every entry at or before time, and 0 when there is none.
• charge returns whether the charge goes through in that reading of everything recorded so far, itself included.
• A refused charge stays in the ledger and is read again with every later answer. A grant recorded later but dated at or before it can let it through. In the same way, a charge recorded later but dated earlier can use credits that a charge dated after it needed, and that charge is then refused. What charge returned stays what was true when it was called.

Example

ledger = CreditLedger()
ledger.grant(10, 50)
ledger.charge(30, 40)   # True: 50 credits at 30
ledger.charge(20, 30)   # True: 50 credits at 20
ledger.balance_at(25)   # 20
ledger.balance_at(30)   # 20: only 20 left at 30, so the charge at 30 is refused
ledger.grant(5, 30)
ledger.balance_at(30)   # 10: with 80 granted, both charges go through

Notes

• Times are integers from 0 up; amounts are positive integers. Inputs are always valid.
• balance_at changes nothing.

Done when Submit goes green.