Implement expiring credit ledger

Implement an expiring-credit ledger that supports out-of-order events. Expose three functions with the following semantics: - add_credit(id, amount, time_stamp, expiration): Add a credit bucket identified by id with amount units that becomes active at time_stamp and expires at time_stamp + expiration (half-open interval [start, end)). - charge(amount, time_stamp): At the given time_stamp, deduct amount from all credits that are active at that time, always consuming from the credit with the earliest expiration first; if multiple credits share the same expiration, break ties by earlier activation time, then by lexicographical id. Return the amount actually charged (do not deduct from inactive or expired credits). - get_balance(time_stamp): Return the total remaining amount across all credits active at time_stamp. Events for add_credit and charge may arrive in arbitrary order of time_stamp, so the data structure must support retroactive inserts and queries correctly. Design for efficiency and specify time/space complexities of your approach. Example: add_credit("c1", 20, 10, 30) // active [10, 40) add_credit("c2", 20, 40, 30) // active [40, 70) add_credit("c3", 20, 20, 30) // active [20, 50) add_credit("c4", 20, 30, 30) // active [30, 60) charge(45, 30) // consume c1->0, c3->0, c4->15 get_balance ( 10) => 20 // c1 get_balance ( 30) => 15 // c4=15 get_balance ( 55) => 35 // c4=15, c2=20