Implement Time-Aware GPU Credit Ledger

Problem Statement

AI compute platforms often issue GPU credits with varying expiration dates (e.g., promotional grants, monthly subscription allowances, and reserved instance buffers). When a user runs a workload, credits should be deducted from grants that expire the earliest to prevent premature expiration waste.

Implement the CreditLedger class to manage time-aware GPU credit balances:

• __init__(): Initializes the ledger with no credits.
• add_grant(grant_id: str, amount: int, expire_at: int) -> None: Adds a grant of amount credits that remains valid for timestamps t bool: Attempts to consume amount credits at timestamp. Credits must be drawn from valid (unexpired) grants prioritizing the ones with the earliest expire_at. If the total valid credits at timestamp is less than amount, the transaction fails atomically (no credits are deducted) and returns False. Otherwise, credits are deducted and it returns True.
• get_balance(timestamp: int) -> int: Returns the total amount of unexpired credits available at timestamp.

Note: Calls to consume and get_balance are guaranteed to have monotonically non-decreasing timestamps (timestamp_{i} >= timestamp_{i-1}).

Interface

class CreditLedger:
    def __init__(self):
        pass

    def add_grant(self, grant_id: str, amount: int, expire_at: int) -> None:
        pass

    def consume(self, timestamp: int, amount: int) -> bool:
        pass

    def get_balance(self, timestamp: int) -> int:
        pass

Examples

Example 1

ledger = CreditLedger()
ledger.add_grant("g1", 100, 50)  # 100 credits expiring at t=50
ledger.add_grant("g2", 50, 30)   # 50 credits expiring at t=30

# At t=10, consume 80 credits.
# Priority goes to g2 (expires at 30). Takes 50 from g2 and 30 from g1.
assert ledger.consume(10, 80) == True

# Remaining: 70 credits in g1 expiring at 50.
assert ledger.get_balance(20) == 70

# At t=40, g1 is still valid (40 < 50).
assert ledger.consume(40, 70) == True
assert ledger.get_balance(45) == 0

Example 2

ledger = CreditLedger()
ledger.add_grant("g1", 50, 20)

# At t=20, g1 has expired (valid only for t < 20).
assert ledger.get_balance(20) == 0
assert ledger.consume(20, 10) == False

Constraints

• 1 <= amount <= 10^9
• 1 <= timestamp, expire_at <= 10^14
• grant_id is a unique non-empty alphanumeric string.
• Timestamps in consume and get_balance are monotonically non-decreasing.
• Up to 2 * 10^5 calls across all methods.

Edge Cases

• Grants added with expire_at <= current_time.
• A consume request exceeding available balance should not alter any grant balances.
• Multiple grants having identical expire_at timestamps.