Process Tasks Using Servers — Medium Problem & Solution
servers[i] is the weight of server i, and tasks[j] is how many seconds task j needs. Task j is queued at second j.
- Difficulty: Medium
- Topics: Arrays, Simulation, Heap
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
servers[i] is the weight of server i, and tasks[j] is how many seconds task j needs. Task j is queued at second j.
At each second, as long as the queue is non-empty and a server is free, the front task is assigned to the free server with the smallest weight, breaking ties by the smallest index. If every server is busy, the queue waits until one frees up, and then the waiting tasks are assigned in order. Return the server index each task is assigned to.
Example 1
Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
Output: [2,2,0,2,1,2]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]Example 3
Input: servers = [1], tasks = [5,5]
Output: [0,0]
Explanation: One server runs both, the second after the first finishes.Constraints
servers.length == ntasks.length == m1 <= n, m <= 20001 <= servers[i], tasks[j] <= 2 * 10^5
How to solve Process Tasks Using Servers
Simulate with two priority queues — free servers keyed on (weight, index) and busy servers keyed on finish time. Task j starts at second j if anything is free, and otherwise at the moment the first server frees up.
Approach
- Before task
j, return every server whose finish time is at most the current second to the free pool. - If the free pool is empty, advance the clock to the earliest finish and return those servers.
- Assign the task to the smallest
(weight, index)free server and record it. - Move that server to the busy pool with finish time
start + tasks[j].
Why it works
The queue never needs to be modelled explicitly: because tasks arrive one per second and are served strictly in order, handling task j in a loop already gives FIFO. Jumping the clock rather than ticking is what keeps the simulation linear in the task count instead of the time range.
Complexity
- Time —
O((n + m) log n) - Space —
O(n + m)
Pitfalls
- Ties on weight go to the smaller server index, not to whichever was freed first.
- A task that waits starts when the server frees, not at second
j. - Servers freed at exactly the current second are available.
Reference solution
Python
from typing import List
import heapq
def assignTasks(servers: List[int], tasks: List[int]) -> List[int]:
free = [(w, i) for i, w in enumerate(servers)]
heapq.heapify(free)
busy = []
out = []
for j, need in enumerate(tasks):
while busy and busy[0][0] <= j:
_, w, i = heapq.heappop(busy)
heapq.heappush(free, (w, i))
if not free:
start = busy[0][0]
while busy and busy[0][0] <= start:
_, w, i = heapq.heappop(busy)
heapq.heappush(free, (w, i))
else:
start = j
w, i = heapq.heappop(free)
out.append(i)
heapq.heappush(busy, (start + need, w, i))
return outJavaScript
var assignTasks = function(servers, tasks) {
var m = servers.length, i, t;
var freeAt = [];
for (i = 0; i < m; i++) freeAt.push(0);
var out = [];
for (var j = 0; j < tasks.length; j++) {
var avail = [];
for (i = 0; i < m; i++) if (freeAt[i] <= j) avail.push(i);
var start = j;
if (avail.length === 0) {
start = freeAt[0];
for (i = 1; i < m; i++) if (freeAt[i] < start) start = freeAt[i];
for (i = 0; i < m; i++) if (freeAt[i] <= start) avail.push(i);
}
var pick = avail[0];
for (t = 1; t < avail.length; t++) {
var s = avail[t];
if (servers[s] < servers[pick] || (servers[s] === servers[pick] && s < pick)) pick = s;
}
out.push(pick);
freeAt[pick] = start + tasks[j];
}
return out;
};Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.