AlgoInsight

DSA problem

Process Tasks Using Servers

MediumHeapsPattern: Heapstop300AmazonMicrosoftGoogleBloombergApple

You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the i-th server, and tasks[j] is the time needed to process the j-th task in seconds. Tasks are assigned to the servers using a task queue. Initially, all servers are free, and the queue is empty.

At second j, the j-th task is inserted into the queue (starting with the 0-th task being inserted at second 0). As long as there are free servers and the queue is not empty, the task in the front of the queue will be assigned to a free server with the smallest weight; if there is a tie, it is assigned to a free server with the smallest index. If there are no free servers and the queue is not empty, we wait until a server becomes free. Note that the server processes the task and then is free again, but only at the second the task finishes processing — it cannot accept a new task at the very same second unless it has already become free at an earlier moment.

The natural data structures are two min-heaps. An "idle" heap orders free servers by (weight, originalIndex). A "busy" heap orders working servers by (freeAt, weight, originalIndex). Each second we either dispatch the next ready task to the best idle server, or jump time forward to the moment the earliest busy server frees up — whichever applies.

Returning the array ans of length m where ans[j] is the index of the server the j-th task is assigned to: process tasks in order, maintain a simulated clock time that starts at 0, and always migrate every server whose freeAt <= time from the busy heap back into the idle heap before assigning the next task. The whole algorithm is O((n + m) log n).

Examples

Example 1
Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
Output: [2,2,0,2,1,2]
Explanation: At t=0 task 0 → server 2 (weight 2). At t=1 server 2 frees; tasks 1,2 are queued; assign task 1 → server 2. At t=2 server 2 still busy until t=3; task 2 → server 0 (weight 3, index 0). And so on.
Example 2
Input: servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
Output: [1,4,1,4,1,3,2]
Explanation: Smallest-weight idle server (with tie-break on index) always takes the next task; this is a step-by-step simulation.
Example 3
Input: servers = [10], tasks = [1,1,1]
Output: [0,0,0]
Explanation: Only one server exists, so it processes every task sequentially.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

heappriority-queuesimulationarray

Browse all DSA problems