Track Expiring GPU Credits

Implement a GPU credit tracking system that processes time-stamped events arriving out of order. Operations: - `add_credit(amount, start_time, duration)`: create a credit grant that is valid for every integer timestamp in the inclusive interval `[start_time, start_time + duration]` - `subtract(amount, timestamp)`: record usage at a timestamp - `get_balance(timestamp)`: return the effective balance at that time Rules: - Events may be inserted in any order, so queries must behave as if all events were replayed in timestamp order. - When subtracting, consume only credits that are active at that timestamp. - If multiple active grants are available, consume the one that expires soonest first. - If expiration times tie, consume the grant with earlier start time first. - If usage exceeds the active balance, keep the remainder as debt. - For a query, return `None` if there is no active credit history at that timestamp or if the effective balance is negative. Return `0` only when grants existed and were exactly exhausted. Common follow-ups: 1. Produce an audit log showing which credit grants funded each subtraction and by how much. 2. Refactor the solution into event, grant, and audit record classes. 3. Scale to about `1e5` events and frequent queries using sorted event storage, replay optimizations, or periodic snapshots. This question tests event replay, time-window logic, priority selection, out-of-order processing, and engineering trade-offs.