GPU Credit Management System

Design a GPU credit management system for a cloud computing platform. Credits are granted with specific validity windows and can be consumed (subtracted) at specific timestamps.

Due to network delays in a distributed system, operations may arrive out of order - you might receive a consumption event for timestamp 30 before processing a grant that covers that time.

Implement the CreditSystem class with the following methods:

• CreditSystem() - Initialize an empty credit system
• grantCredit(id, amount, startTime, expirationTime) - Add a new credit grant with a unique ID. The credit is active during the interval [startTime, expirationTime - 1] inclusive.
• subtract(amount, timestamp) - Consume credits at a specific timestamp. This only affects the balance at that exact timestamp, not future timestamps.
• getBalance(timestamp) - Return the available credits at the given timestamp. If usage exceeds available credits at that time, return -1.

Key Insight: Subtraction at timestamp T only reduces the balance at time T, not at T+1 or any other time. Each timestamp maintains its own balance history.

Example: grantCredit("a", 3, 10, 60) // 3 credits active for t ∈ [10, 59] getBalance(10) // Returns 3 grantCredit("b", 2, 20, 40) // 2 credits active for t ∈ [20, 39] subtract(1, 30) // Remove 1 credit at t=30 getBalance(30) // Returns 4 (5 - 1) getBalance(35) // Returns 5 (subtraction at t=30 doesn't affect t=35)

Related: See "GPU Credit Management - Optimized Queries" for a follow-up with O(1) query optimization.