Process Tasks Using Servers

Medium
979.

Process Tasks Using Servers

Process Tasks Using Servers is a medium coding problem on arrays, simulation and heap, asked in Amazon, Google, Microsoft and Twitter interviews.

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 == n
  • tasks.length == m
  • 1 <= n, m <= 2000
  • 1 <= servers[i], tasks[j] <= 2 * 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} servers
 * @param {number[]} tasks
 * @return {number[]}
 */
var assignTasks = function(servers, tasks) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Process Tasks Using Servers — Solution in Python, Java & C++

Process Tasks Using Servers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Process Tasks Using Servers is a medium coding problem on arrays, simulation and heap, asked in Amazon, Google, Microsoft and Twitter interviews.

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 == n
  • tasks.length == m
  • 1 <= n, m <= 2000
  • 1 <= servers[i], tasks[j] <= 2 * 10^5

Hints for Process Tasks Using Servers

  1. Hint 1

    Two pools: servers that are free, and servers that are busy with a finish time.

  2. Hint 2

    The free pool is ordered by (weight, index); the busy pool by finish time.

  3. Hint 3

    If nothing is free when a task arrives, jump the clock to the earliest finish rather than ticking.

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

  1. Before task j, return every server whose finish time is at most the current second to the free pool.
  2. If the free pool is empty, advance the clock to the earliest finish and return those servers.
  3. Assign the task to the smallest (weight, index) free server and record it.
  4. 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 out

Java

public static int[] assignTasks(int[] servers, int[] tasks) {
    int m = servers.length;
    long[] freeAt = new long[m];
    int[] out = new int[tasks.length];
    for (int j = 0; j < tasks.length; j++) {
        List<Integer> avail = new ArrayList<>();
        for (int i = 0; i < m; i++) if (freeAt[i] <= j) avail.add(i);
        long start = j;
        if (avail.isEmpty()) {
            start = freeAt[0];
            for (int i = 1; i < m; i++) start = Math.min(start, freeAt[i]);
            for (int i = 0; i < m; i++) if (freeAt[i] <= start) avail.add(i);
        }
        int pick = avail.get(0);
        for (int s : avail) {
            if (servers[s] < servers[pick] || (servers[s] == servers[pick] && s < pick)) pick = s;
        }
        out[j] = pick;
        freeAt[pick] = start + tasks[j];
    }
    return out;
}

C++

vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
    int m = (int) servers.size();
    vector<long long> freeAt(m, 0);
    vector<int> out;
    for (int j = 0; j < (int) tasks.size(); j++) {
        vector<int> avail;
        for (int i = 0; i < m; i++) if (freeAt[i] <= j) avail.push_back(i);
        long long start = j;
        if (avail.empty()) {
            start = freeAt[0];
            for (int i = 1; i < m; i++) start = min(start, freeAt[i]);
            for (int i = 0; i < m; i++) if (freeAt[i] <= start) avail.push_back(i);
        }
        int pick = avail[0];
        for (int s : avail) {
            if (servers[s] < servers[pick] || (servers[s] == servers[pick] && s < pick)) pick = s;
        }
        out.push_back(pick);
        freeAt[pick] = start + tasks[j];
    }
    return out;
}

JavaScript

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Heaps and Priority Queues