Manage GPU Credits with Expiration

Question

Implement a GPU credit manager supporting out-of-order operations:

API

add_credit(id, amount, timestamp, expiration) // adds ‘amount’ credits usable in [timestamp, timestamp+expiration)

charge(amount, timestamp) // consume ‘amount’ credits at ‘timestamp’; always draw from credits that expire soonest first (tie-break by any order)

get_balance(timestamp) // return total unexpired credits available at ‘timestamp’

Constraints

add_credit and charge calls may arrive in arbitrary time order

charge(…) must fail silently or partially apply only if enough total balance exists at that moment

Design an efficient data structure to support ~10^5 operations with O(log n) per call.

Manage GPU Credits with Expiration

You are given a list of GPU credit manager API calls in the order they arrive. Each credit batch has an amount, a start timestamp, and an expiration duration, so it is usable during the half-open interval [timestamp, timestamp + expiration). Calls may mention timestamps in any order.

Process the operations in the given input order:

• ("add", id, amount, timestamp, expiration): add a new credit batch. The id is unique metadata.
• ("charge", amount, timestamp): try to consume amount credits at the given timestamp.
• ("balance", timestamp): return the total currently remaining credits that are usable at that timestamp.

Rules:

1. A successful charge may use only batches that are active at that timestamp.
2. It must always consume from the active batches that expire soonest first. If multiple batches expire at the same time, any order among them is acceptable.
3. If the total active balance at that timestamp is smaller than the requested amount, the charge fails and nothing changes.
4. Operations are processed in the order they appear in the input. A later operation may refer to an earlier timestamp, but it does not retroactively change results that were already returned earlier.

Return a list containing the result of every non-add operation, in order:

• For a charge, append True if it succeeds, otherwise False.
• For a balance query, append the integer balance.

Examples

Example 1

Input: ([('balance', 5), ('add', 'a', 10, 5, 5), ('balance', 7), ('charge', 4, 8), ('balance', 8), ('balance', 10)],)
Output: [0, 10, True, 6, 0]

Explanation: Initially there are no credits. Batch 'a' is active for times 5 through 9. Charging 4 at time 8 succeeds, leaving 6. At time 10 the batch is expired because the interval is half-open.

Example 2

Input: ([('add', 'a', 5, 10, 10), ('add', 'b', 7, 5, 10), ('charge', 5, 12), ('balance', 12), ('balance', 17), ('charge', 6, 9), ('balance', 17)],)
Output: [True, 7, 5, False, 5]

Explanation: At time 12 both batches are active, and batch 'b' expires first, so the charge uses 5 from 'b'. That leaves 2 in 'b' and 5 in 'a'. A later failed charge at earlier time 9 does not change the state.

Hints

1. A credit batch contributes its remaining amount to every query timestamp inside its active interval, so add/remove actions can be modeled as range updates with point queries.
2. To enforce 'expire soonest first' at one timestamp, think about an interval structure where each batch is stored on O(log n) nodes, and a point query inspects only one root-to-leaf path.

Approach

We process the operations in input order, keeping every credit batch in a flat list batches, where each entry is [remaining, start, end, add_order]. A batch is active at a timestamp t exactly when start <= t < end (half-open interval), with end = timestamp + expiration.

add — append [amount, timestamp, timestamp + expiration, add_order] and bump add_order. The id is just metadata; add_order is a stable tie-breaker.

balance — linearly scan all batches and sum remaining for those that are active and still have credit (remaining > 0 and start <= t < end). Return that total.

charge — first scan every batch and collect the active ones as tuples (end, order, index), accumulating their total balance.

• If total < amount, the charge can't be covered, so append False and change nothing (rule 3 — failed charges are atomic).
• Otherwise sort the active tuples. Sorting by (end, order) puts the soonest-expiring batches first (rule 2), with add_order breaking ties deterministically. We then greedily walk that order, taking min(need, batches[i][0]) from each batch until need hits 0, decrementing the stored remaining in place. Append True.

Why it's correct: because we only sum/spend active batches, expired or not-yet-started credit is never touched. Consuming soonest-to-expire first is the standard greedy that maximizes future usable balance. Since we verified total >= amount before spending, the greedy loop always fully satisfies need, so the in-place deductions leave state consistent for later operations — and earlier returned results are never mutated.

• Time complexity: Worst-case O(n^2 log n), where n is the number of operations. Each balance/charge does an O(n) scan over all batches; a charge additionally sorts up to n active batches in O(n log n). With up to O(n) charge operations, the total is O(n^2 log n).
• Space complexity: O(n) — the batches list grows by one entry per add (up to n entries), plus the active/results lists which are O(n) in the worst case.