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

Solution

def solution(user_caps, user_org, org_caps, operations):
    import heapq
    from collections import defaultdict

    INF = 10 ** 30

    user_balance = defaultdict(int)
    org_balance = defaultdict(int)
    user_lots = defaultdict(list)      # user -> min-heap of (expire_time, lot_id)
    expire_heap = []                   # global min-heap of (expire_time, lot_id)
    top_heap = []                      # max-heap simulated with (-balance, user)
    lot_info = {}                      # lot_id -> [remaining_amount, user, org, expire_time]
    next_lot_id = 0

    def push_top(user):
        bal = user_balance[user]
        if bal > 0:
            heapq.heappush(top_heap, (-bal, user))

    def process_expired(t):
        while expire_heap and expire_heap[0][0] <= t:
            _, lot_id = heapq.heappop(expire_heap)
            info = lot_info.pop(lot_id, None)
            if info is None:
                continue
            remaining, user, org, _ = info
            if remaining <= 0:
                continue
            user_balance[user] -= remaining
            if org is not None:
                org_balance[org] -= remaining
            push_top(user)

    def add_credits(user, amount, expire_time, current_time):
        nonlocal next_lot_id

        if amount <= 0:
            return 0
        if expire_time is not None and expire_time <= current_time:
            return 0

        org = user_org.get(user)
        user_cap = user_caps.get(user, INF)
        org_cap = INF if org is None else org_caps.get(org, INF)

        user_room = user_cap - user_balance[user]
        org_room = org_cap - (org_balance[org] if org is not None else 0)
        actual = min(amount, user_room, org_room)

        if actual <= 0:
            return 0

        exp = INF if expire_time is None else expire_time
        lot_id = next_lot_id
        next_lot_id += 1

        lot_info[lot_id] = [actual, user, org, exp]
        heapq.heappush(user_lots[user], (exp, lot_id))
        if exp != INF:
            heapq.heappush(expire_heap, (exp, lot_id))

        user_balance[user] += actual
        if org is not None:
            org_balance[org] += actual
        push_top(user)
        return actual

    def consume(user, amount):
        if amount < 0:
            return False
        if user_balance[user] < amount:
            return False
        if amount == 0:
            return True

        remaining_to_consume = amount
        heap = user_lots[user]

        while remaining_to_consume > 0:
            while heap:
                exp, lot_id = heapq.heappop(heap)
                info = lot_info.get(lot_id)
                if info is None:
                    continue

                remaining, lot_user, org, _ = info
                take = min(remaining, remaining_to_consume)
                new_remaining = remaining - take
                remaining_to_consume -= take

                if new_remaining == 0:
                    del lot_info[lot_id]
                else:
                    info[0] = new_remaining
                    heapq.heappush(heap, (exp, lot_id))
                break
            else:
                return False

        org = user_org.get(user)
        user_balance[user] -= amount
        if org is not None:
            org_balance[org] -= amount
        push_top(user)
        return True

    def top_k(k):
        if k <= 0:
            return []

        result = []
        popped_valid = []
        seen = set()

        while top_heap and len(result) < k:
            neg_bal, user = heapq.heappop(top_heap)
            bal = -neg_bal
            current = user_balance[user]

            if current <= 0 or bal != current or user in seen:
                continue

            result.append([user, current])
            popped_valid.append((neg_bal, user))
            seen.add(user)

        for item in popped_valid:
            heapq.heappush(top_heap, item)

        return result

    results = []

    for op in operations:
        kind = op[0]
        t = op[1]
        process_expired(t)

        if kind == 'grant':
            _, _, user, amount, expire_time = op
            results.append(add_credits(user, amount, expire_time, t))
        elif kind == 'refund':
            _, _, user, amount = op
            results.append(add_credits(user, amount, None, t))
        elif kind == 'consume':
            _, _, user, amount = op
            results.append(consume(user, amount))
        elif kind == 'get':
            _, _, user = op
            results.append(user_balance[user])
        elif kind == 'topK':
            _, _, k = op
            results.append(top_k(k))
        else:
            raise ValueError('Unknown operation: ' + str(kind))

    return results

Time complexity: Amortized O((1 + r) log n) per operation, where r is the number of credit lots consumed or expired during that call; `topK(k)` is O(k log n).. Space complexity: O(U + L + Q) worst-case with lazy heap entries, where U is the number of users, L is the number of live lots, and Q is the number of operations; this is near-linear in the input size..

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.