Track Expiring GPU Credits

Problem Statement

AI compute platforms often issue promotional or contractual compute credits that expire after a specified duration. When training workloads consume GPU hours, the platform must prioritize consuming credits that expire the earliest to maximize the user's usable credit value.

Implement the GPUCreditTracker class to simulate a real-time credit ledger that supports granting credits, consuming credits, and querying the current balance with debt handling.

Interface

class GPUCreditTracker:
    def __init__(self):
        pass

    def grant(self, amount: int, timestamp: int, expiry: int) -> None:
        """Grants compute credits valid from timestamp until expiry (exclusive)."""
        pass

    def consume(self, amount: int, timestamp: int) -> int:
        """Consumes credits at timestamp. Returns the outstanding debt after consumption."""
        pass

    def get_balance(self, timestamp: int) -> int:
        """Returns net active credits at timestamp, or negative value representing debt."""
        pass

Rules

1. Priority Consumption: Credits that expire earliest must be consumed first.
2. Expiration: A grant with expiration expiry cannot be used at any timestamp >= expiry.
3. Debt Tracking: If a consumption request exceeds total available active credits, all active credits are consumed, and the remaining unsatisfied amount becomes outstanding debt (represented as a negative balance).
4. Debt Settlement: When a new grant is added while outstanding debt exists, incoming credits must immediately offset the debt first. Any remaining credits after clearing the debt are retained with the given expiry.
5. Monotonicity: All calls to grant, consume, and get_balance have non-decreasing timestamps (timestamp >= previous_timestamp).

Examples

Example 1

tracker = GPUCreditTracker()

# Grant 100 credits at t=0 expiring at t=10
tracker.grant(amount=100, timestamp=0, expiry=10)

# Grant 50 credits at t=2 expiring at t=5
tracker.grant(amount=50, timestamp=2, expiry=5)

# Consume 70 credits at t=3
# Earliest-expiring credits (expiry=5) are used first: 50 used.
# Remaining 20 credits are taken from the expiry=10 batch (80 left).
# Outstanding debt is 0.
assert tracker.consume(amount=70, timestamp=3) == 0

# Balance at t=4 is 80
assert tracker.get_balance(timestamp=4) == 80

# Consume 90 credits at t=8
# Only 80 active credits remain. 80 are consumed, 10 become debt.
assert tracker.consume(amount=90, timestamp=8) == 10
assert tracker.get_balance(timestamp=8) == -10

# Grant 30 credits at t=12 expiring at t=20
# 10 credits immediately settle the debt; 20 credits remain active.
tracker.grant(amount=30, timestamp=12, expiry=20)
assert tracker.get_balance(timestamp=12) == 20

Example 2: Expiration Handling

tracker = GPUCreditTracker()
tracker.grant(amount=50, timestamp=0, expiry=5)

# At t=5, the 50 credits have expired
assert tracker.get_balance(timestamp=5) == 0

# Consuming at t=6 leads directly to debt
assert tracker.consume(amount=20, timestamp=6) == 20
assert tracker.get_balance(timestamp=6) == -20

Constraints

• 1 = t_prev.
• At most 2 * 10^5 total method calls.

Edge Cases

• Consuming when the active balance is 0 increases existing debt.
• Grants that are immediately swallowed by existing debt should not be added to the expiration queue.
• Multiple grants with the exact same expiry timestamp.