Manage GPU Credits with Expiration

Question

Implement a GPU credit manager supporting out-of-order operations:

API

add_credit(id, amount, timestamp, expiration) // adds ‘amount’ credits usable in [timestamp, timestamp+expiration)

charge(amount, timestamp) // consume ‘amount’ credits at ‘timestamp’; always draw from credits that expire soonest first (tie-break by any order)

get_balance(timestamp) // return total unexpired credits available at ‘timestamp’

Constraints

add_credit and charge calls may arrive in arbitrary time order

charge(…) must fail silently or partially apply only if enough total balance exists at that moment

Design an efficient data structure to support ~10^5 operations with O(log n) per call.