The Question

Maximum GPU Tasks with Credit Regeneration

You are managing a GPU cluster that uses a credit-based system for job execution. You start with initial_credits and a max_capacity. Credits regenerate at a constant regeneration_rate per unit of time. You are given a list of tasks, where each task is [timestamp, cost]. A task can only be executed if your current credit balance is at least equal to the task's cost at that timestamp. If you choose to execute a task, the cost is immediately deducted from your balance. If you cannot afford a task, you may choose to 'undo' a previously executed task to reclaim its credits (though the time spent is not recovered). Determine the maximum number of tasks you can complete given the task schedule. Assume for this optimization that reclaiming credits from a past task ignores the capacity limit for the reclaimed amount.

Python

Greedy

Priority Queue

Sorting

Token Bucket

Questions & Insights

Clarifying Questions

Is there a maximum credit capacity?

Assumption: We will assume a "Token Bucket" model where credits regenerate up to a maximum capacity

C

. If no capacity is specified, we assume

C = \infty

Are tasks provided in chronological order?

Assumption: Tasks are given as a list of (timestamp, cost). We assume they are not necessarily sorted and will sort them ourselves.

Can we skip tasks to save credits for more expensive or future tasks?

Assumption: Yes, the goal is to maximize the total number of tasks completed. This implies a greedy strategy with the ability to "undo" or skip the least efficient choices.

What is the scale of the input?

Assumption:

N

umber of tasks) up to

10^5

, timestamps up to

10^9

. This requires an

O(N \log N)

solution.

Thinking Process

Credit Regeneration Logic: Credits increase linearly with time. Between two tasks at

T_{i-1}

and

T_i

, the credits gained is

(T_i - T_{i-1}) \times \text{rate}

. This value must be clamped by the max_capacity.

Greedy Strategy: To maximize the number of tasks, if we encounter a task we cannot afford, we have two choices: skip the current task or "undo" a previously completed task that had a higher cost. By undoing a more expensive task, we free up more credits for the current and future tasks.

Data Structure Selection: Use a Max-Heap to keep track of the costs of all tasks currently "accepted." If the credit balance drops below zero after attempting a task, we remove the largest cost item from the heap and add its cost back to our balance.

Handling the Capacity Cap: With a capacity cap, "undoing" a task is tricky because credits we didn't spend in the past might have been lost if the bucket hit its limit. To ensure a robust solution, we will assume the standard "Priority Queue Greedy" works for the version where we want to complete as many tasks as possible without a capacity cap, or provide the logic for a strictly sequential "accept/reject" rate-limiter.

Implementation Breakdown

Problem Set

Functional Requirements:

Calculate current credit balance based on time elapsed.

Maximize the number of tasks processed.

Handle high-frequency task arrival.

Constraints:

Time Complexity:

O(N \log N)

Space Complexity:

O(N)

for the heap.

Credit balance can never stay negative.

Approach

Algorithm: Greedy with Max-Heap (Priority Queue).

Data Structure: Python heapq (implemented as min-heap, so we store negative costs to simulate a max-heap).

Complexity:

Time:

O(N \log N)

due to sorting and heap operations.

Space:

O(N)

to store tasks in the heap.

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: In a production system, credit calculations should use Decimal or fixed-point arithmetic to avoid floating-point precision errors (e.g.,

0.1 + 0.2 \neq 0.3

Streaming/Iterative version: For a real-time system, we wouldn't sort. We would maintain the current_credits and last_time as state in a class (Token Bucket Algorithm) and use a simple is_allowed(task) check.

Distributed Systems: In a distributed environment, credit balances are often stored in a fast cache like Redis. To handle race conditions (two tasks using credits at the same time), use Lua scripts or the SETNX lock to ensure atomicity of the get-calculate-set cycle.

Capacity Impact: Note that if a strict capacity is enforced, the "undo" greedy logic is a heuristic. If capacity is finite, removing an old expensive task might not "retroactively" increase your current credits as much as expected if the bucket would have capped in the interim. For a strict capacity constraint with the ability to skip tasks, the problem evolves into a dynamic programming challenge.