Build a SaaS API-Credit Ledger With Expiring Grants and Late Events

You're building the credit accounting layer behind a metered API product. An account receives credits through grants (e.g. a monthly plan allotment, or a one-off top-up), spends credits through usage, and can be asked for its current balance. Every grant expires, and any credits still sitting in an expired grant are lost — they do not roll over and cannot be spent after expiration.

Implement three operations on a single account:

• grant(grant_id, amount, timestamp, expiration) — adds amount credits usable during [timestamp, expiration).
• subtract(amount, timestamp) — spends amount credits as of timestamp.
• get_balance(timestamp) — returns the credits usable at timestamp.

Two things make this harder than a running total:

• Expiration priority. When subtract spends credits, it draws first from whichever usable grant expires soonest, then the next soonest, and so on — so credits that are about to expire get used before credits with more runway.
• Out-of-order arrival. Calls do not necessarily arrive in timestamp order — a grant or subtract can show up with an earlier timestamp than an operation already processed. Every get_balance(t) must reflect every operation received so far with a timestamp at or before t, regardless of the order they arrived in.

Assumptions

• Single account (multiple accounts are independent copies of this structure).
• All amounts and timestamps are positive integers; every grant has expiration > timestamp; grant_id values are unique.
• A grant is usable in the half-open interval [timestamp, expiration) — usable at its start instant, not usable at its expiration instant.
• At a tie between a grant and a subtract with the same timestamp, the grant is considered to apply first.
• If a subtract asks for more than is usable at its timestamp, spend whatever is available and do not go into debt (no error, no negative balance).

Function Signature

class CreditLedger:
    def grant(self, grant_id: str, amount: int, timestamp: int, expiration: int) -> None: ...
    def subtract(self, amount: int, timestamp: int) -> None: ...
    def get_balance(self, timestamp: int) -> int: ...

Example

ledger = CreditLedger()
ledger.grant("g1", 100, timestamp=0, expiration=100)
ledger.get_balance(10)                       # 100
ledger.subtract(30, timestamp=20)
ledger.get_balance(20)                       # 70
ledger.grant("g2", 50, timestamp=5, expiration=15)   # arrives "late": timestamp 5 is before the subtract at 20
ledger.get_balance(10)                       # 150 (g1 and g2 both usable at t=10)
ledger.get_balance(16)                       # 100 (g2 expired by 16; the subtract at t=20 hasn't happened yet)
ledger.get_balance(100)                      # 0   (g1 expires at exactly 100, not usable there)

Part 1 — Correct ledger

Implement all three operations so that every answer is correct regardless of arrival order. State the time and space complexity of each operation in terms of the number of operations received so far, N.