Design a Time-Windowed GPU Credit Ledger

Problem Statement

AI compute platforms often issue GPU credits to customers through grants that are valid only within specific time windows. Customers consume these credits by running workloads. In distributed environments, credit grants and consumption events can arrive out of order.

Implement an in-memory credit ledger GPULedger that supports time-delimited grants and consumptions. Consumptions must always allocate credits from the eligible grants that expire earliest (Earliest Deadline First). Because completed compute jobs cannot be undone, an out-of-order consumption request must be rejected if accepting it would retroactively cause any currently accepted consumption to lack sufficient credits at its respective execution time.

Implement the following interface:

class GPULedger:
    def __init__(self):
        pass

    def add_grant(self, grant_id: str, amount: int, start_time: int, end_time: int) -> None:
        """Adds a grant of credits active in the inclusive window [start_time, end_time]."""
        pass

    def consume(self, event_id: str, amount: int, timestamp: int) -> bool:
        """Attempts to consume credits at `timestamp`.
        Returns True if the consumption is accepted, or False if rejected.
        """
        pass

    def get_balance(self, timestamp: int) -> int:
        """Returns the total remaining unexpired and unconsumed credits available at `timestamp`."""
        pass

Rules and Allocation Semantics

1. Grant Validity: A grant g is eligible to cover a consumption at timestamp if and only if g.start_time <= timestamp <= g.end_time.
2. Credit Priority: When multiple grants are active at a consumption's timestamp, credits must be drawn first from the grant with the smallest end_time. If there is a tie, draw from the grant with the lexicographically smaller grant_id.
3. Replay & Atomicity: If a consumption cannot be fully satisfied at timestamp, or if accepting it would cause any existing accepted consumption (at any time t >= timestamp) to fail due to credit exhaustion, the entire consumption must be rejected (return False) without altering ledger state.
4. Idempotency: Grant IDs and event IDs are unique. You do not need to handle duplicate IDs with different parameters.

Constraints

• 1 <= amount <= 10^9
• 0 <= start_time <= end_time <= 10^9
• 0 <= timestamp <= 10^9
• Up to 2,000 total calls across all methods.

Examples

Example 1: Standard Chronological Flow

ledger = GPULedger()
ledger.add_grant("g1", 100, 0, 10)
ledger.add_grant("g2", 50, 5, 15)

# At t=6, both g1 and g2 are active. g1 expires earlier (10 < 15), so it is consumed first.
assert ledger.consume("c1", 80, 6) == True   # 20 remaining in g1, 50 in g2
assert ledger.get_balance(6) == 70

# At t=11, g1 is expired. Only g2 is active with 50 credits.
assert ledger.consume("c2", 60, 11) == False # Rejected: only 50 available
assert ledger.consume("c3", 40, 11) == True  # Accepted: 10 remaining in g2
assert ledger.get_balance(11) == 10

Example 2: Out-of-Order Consumption Arrival

ledger = GPULedger()
ledger.add_grant("g1", 100, 0, 10)

# Future consumption at t=8 consumes 80 credits
assert ledger.consume("c_late", 80, 8) == True

# Out-of-order consumption at t=2 for 30 credits arrives
# If accepted, only 70 credits would remain in g1, causing c_late (requiring 80) to fail.
assert ledger.consume("c_early", 30, 2) == False  # Rejected
assert ledger.get_balance(8) == 20

Edge Cases to Consider

• Consumptions landing exactly on start_time or end_time of a grant.
• Multiple grants having identical start and end windows.
• Queries for balance at times where no grants are active, or where all active grants are completely consumed.