Implement a GPU credit manager

Implement a GPU credit manager for a compute cluster. Each user has a nonnegative credit balance that can be increased (grantCredits(user, amount)), consumed when scheduling jobs (consume(user, amount) -> boolean), and refunded when jobs finish (refund(user, amount)). Support querying a user’s remaining credits (get(user) -> int) and retrieving the top K users by balance (topK(k) -> list). Enforce per-user maximum caps, optional per-organization aggregate caps, and optional credit expirations. Prevent balances from going negative and ensure atomicity under concurrent calls. Target O(log n) time per operation and near-linear space. Describe the data structures, provide pseudocode for each API, and analyze time and space complexity.

Implement a GPU Credit Manager

Process a sequence of timestamped operations for a single-threaded GPU credit manager.

Rules:

• Every user starts with 0 credits.
• user_caps[user] is that user's maximum balance. If a user is missing from user_caps, their cap is unlimited.
• user_org[user] gives the user's organization. If a user is missing from user_org, they have no organization.
• org_caps[org] is the maximum total active balance across all users in that organization. If an organization is missing from org_caps, its cap is unlimited.
• Operations are given in nondecreasing timestamp order and are processed atomically.
• Credits are stored in lots. A granted lot may expire at a specific timestamp. Before processing any operation at time t, all remaining credits from lots with expire_time <= t disappear.
• When consuming credits, always consume from the earliest-expiring active lots first. Non-expiring lots are treated as expiring last.
• grant and refund are partially applied if necessary: add as many credits as possible without violating the user cap or the organization cap.
• Balances can never go negative.
• topK(k) returns up to k users with positive balances, sorted by balance descending, then by user name ascending.

Implement solution(user_caps, user_org, org_caps, operations) and return a list containing the result of every operation in order.

Operation formats:

• ('grant', t, user, amount, expire_time) -> return the integer amount actually added. expire_time is an integer timestamp or None.
• ('refund', t, user, amount) -> return the integer amount actually added. Refunded credits never expire.
• ('consume', t, user, amount) -> return True if the full amount was consumed, otherwise False.
• ('get', t, user) -> return the user's current active balance.
• ('topK', t, k) -> return a list of [user, balance] pairs.

Constraints

• 0 <= len(operations) <= 2 * 10^5
• Operation timestamps are in nondecreasing order
• 0 <= amount, cap <= 10^9
• User and organization names are non-empty strings
• If expire_time is not None, it is an integer timestamp; a lot with expire_time <= t is considered expired before time t operations run

Examples

Example 1

Input: ({}, {}, {}, [])
Output: []

Explanation: With no operations, there are no results to return.

Example 2

Input: ({'alice': 10, 'bob': 7}, {'alice': 'org1', 'bob': 'org1', 'carol': 'org2'}, {'org1': 12, 'org2': 20}, [('grant', 1, 'alice', 8, 5), ('grant', 2, 'bob', 7, None), ('consume', 3, 'alice', 3), ('refund', 4, 'bob', 5), ('get', 4, 'bob'), ('topK', 4, 2), ('get', 5, 'alice'), ('topK', 6, 3)])
Output: [8, 4, True, 3, 7, [['bob', 7], ['alice', 5]], 0, [['bob', 7]]]

Explanation: Bob's first grant is limited by the organization cap, Bob's refund is also capped, and Alice's remaining expiring credits disappear at time 5.

Hints

1. You need two different orderings at once: earliest expiration for consuming/expiring lots, and largest current balance for topK. Heaps plus hash maps are a strong fit.
2. For topK, avoid updating heap entries in place. Push new balance entries and skip stale ones later with lazy deletion.

Approach

This is a stateful simulation. We keep running totals in user_balance and org_balance, and store every grant as an immutable lot in lot_info[lot_id] = [remaining, user, org, expire_time]. Non-expiring lots use the sentinel INF = 10**30 so they sort after every real expiry.

Four heaps drive the logic, all using lazy deletion (stale entries are skipped because lot_info.get(lot_id) returns None or the cached value is outdated):

• expire_heap — global (expire_time, lot_id). Before each op, process_expired(t) pops everything with expire_time <= t, subtracts the lot's remaining from the user/org balances, and drops the lot.
• user_lots[user] — per-user (exp, lot_id) min-heap, so consume always drains the earliest-expiring lots first (matching "consume earliest-expiring first; non-expiring last").
• top_heap — lazy max-heap (-balance, user); top_k pops, validates each entry against the live balance (bal == current and not yet seen), collects the top k, then pushes the valid entries back.

add_credits (used by both grant and refund, with expire_time=None for refunds) computes actual = min(amount, user_cap - user_balance, org_cap - org_balance) — the partial-fill rule — using INF when a cap is absent, then records a new lot.

consume first rejects if balance < amount (so it never goes negative and never partially consumes), then peels take = min(remaining, need) from successive earliest lots, mutating lot_info[lot_id][0] or deleting the lot.

Correctness rests on three invariants kept in lockstep: balances always equal the sum of live-lot remaining, expirations are applied before any op at time t, and caps are checked at insertion time.

• Time complexity: Amortized O((1 + r) log n) per operation, where r is the number of lots expired or partially consumed in that call and n is the number of live heap entries; each lot is pushed/popped O(1) times across its lifetime, so total work is O((Q + L) log(Q + L)). topK(k) is O(k log n).
• Space complexity: O(U + L + Q): U users in the balance maps, L live lots in lot_info, plus lazy (possibly stale) entries across the three heaps bounded by the number of lots/balance updates (O(Q)). Near-linear in input size.