Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1882. Process Tasks Using Servers - Leetcode Solution

Problem Description

You are given two arrays: servers and tasks.

  • servers[i] is the weight (processing power) of the i-th server. Servers are indexed from 0.
  • tasks[j] is the time required to process the j-th task.
Each second, if there are free servers and pending tasks, assign the next task in order to the available server with the smallest weight (if there is a tie, the lowest index wins). Once a server is assigned a task, it becomes unavailable for the duration of that task.
Your goal is to return an array ans where ans[j] is the index of the server that processes the j-th task.
Constraints:
  • Each task is assigned to exactly one server.
  • Servers cannot process more than one task at a time.
  • Tasks arrive at each second in order (i.e., tasks[0] at time 0, tasks[1] at time 1, ...).
  • Servers can be reused after they finish their current task.

Thought Process

At first glance, a brute-force approach would be to check every server for every task at each time step, assigning the task to the first free server with the smallest weight and index. However, this would be inefficient for large inputs.
To optimize, we need to efficiently track which servers are free and which are busy, always being able to quickly get the next available server with the lowest weight and index. This suggests using a data structure like a min-heap (priority queue) for free servers. Additionally, we need to know when busy servers will become free, so we can use another heap to track busy servers by their release time.
The key is to simulate the passage of time, processing tasks in order, and always assigning them to the optimal available server.

Solution Approach

Let's break down the solution step by step:

  1. Initialize Heaps:
    • Use a min-heap for free servers, ordered by (weight, index). This allows us to always pick the best available server.
    • Use another min-heap for busy servers, ordered by (release time, weight, index). This helps us know when each server will be free.
  2. Simulate Time:
    • For each task (arriving at time j), first move any servers that have become free by time j from the busy heap back to the free heap.
    • If there are no free servers, fast-forward time to the earliest server release, and move all servers that become free at that time back to the free heap.
  3. Assign Tasks:
    • Pop the best free server (lowest weight and index) from the free heap.
    • Assign the current task to this server, and push it into the busy heap with its new release time (current time + task duration).
    • Record the server index in the answer array.
  4. Repeat:
    • Continue this process for all tasks, always maintaining the heaps to efficiently assign tasks as soon as possible.

This approach ensures that we always assign tasks to the optimal server and efficiently manage the state of each server as tasks are processed.

Example Walkthrough

Input:
servers = [3,3,2], tasks = [1,2,3,2,1,2]
Step-by-step:

  1. At time 0, all servers are free. Task 0 arrives (duration 1).
    • Free servers: (2,2), (3,0), (3,1) → Choose (2,2). Assign task 0 to server 2.
      Server 2 will be free at time 1.
  2. At time 1, task 1 arrives (duration 2).
    • Server 2 becomes free (release time 1).
      Free servers: (2,2), (3,0), (3,1).
      Assign to (2,2). Server 2 will be free at time 3.
  3. At time 2, task 2 arrives (duration 3).
    • Free servers: (3,0), (3,1).
      Assign to (3,0). Server 0 will be free at time 5.
  4. At time 3, task 3 arrives (duration 2).
    • Server 2 becomes free (release time 3).
      Free servers: (2,2), (3,1).
      Assign to (2,2). Server 2 will be free at time 5.
  5. At time 4, task 4 arrives (duration 1).
    • Free servers: (3,1).
      Assign to (3,1). Server 1 will be free at time 5.
  6. At time 5, task 5 arrives (duration 2).
    • Servers 0, 1, and 2 become free.
      Free servers: (2,2), (3,0), (3,1).
      Assign to (2,2). Server 2 will be free at time 7.
Output: [2,2,0,2,1,2]

Time and Space Complexity

Brute-force approach:
For each task, check every server for availability, resulting in O(n * m) time where n is the number of servers and m is the number of tasks. This is inefficient for large inputs.

Optimized approach (using heaps):

  • Each server and task is pushed and popped from heaps at most once, so heap operations are O(log n).
  • For m tasks, total time complexity is O(m log n).
  • Space complexity is O(n + m) for the heaps and result array.
This is much more efficient and suitable for large inputs.

Summary

The problem requires efficiently assigning tasks to servers based on their availability and processing power. By using two min-heaps—one for free servers and one for busy servers—we can always assign each task to the optimal server in logarithmic time. This approach is both elegant and efficient, making it well-suited for large-scale inputs and real-world scheduling problems.

Code Implementation

import heapq

class Solution:
    def assignTasks(self, servers, tasks):
        n = len(servers)
        m = len(tasks)
        free = []
        busy = []
        for i, w in enumerate(servers):
            heapq.heappush(free, (w, i))
        ans = [0] * m
        time = 0
        for j, duration in enumerate(tasks):
            time = max(time, j)
            # Release servers that are done by current time
            while busy and busy[0][0] <= time:
                _, w, i = heapq.heappop(busy)
                heapq.heappush(free, (w, i))
            # If no free servers, fast-forward time to next server available
            if not free:
                time = busy[0][0]
                while busy and busy[0][0] == time:
                    _, w, i = heapq.heappop(busy)
                    heapq.heappush(free, (w, i))
            w, i = heapq.heappop(free)
            ans[j] = i
            heapq.heappush(busy, (time + duration, w, i))
        return ans
      
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        int n = servers.size(), m = tasks.size();
        // min-heap for free servers: (weight, index)
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> free;
        // min-heap for busy servers: (release time, weight, index)
        priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> busy;
        for (int i = 0; i < n; ++i)
            free.push({servers[i], i});
        vector<int> ans(m);
        long long time = 0;
        for (int j = 0; j < m; ++j) {
            time = max(time, (long long)j);
            while (!busy.empty() && get<0>(busy.top()) <= time) {
                auto [t, w, i] = busy.top(); busy.pop();
                free.push({w, i});
            }
            if (free.empty()) {
                time = get<0>(busy.top());
                while (!busy.empty() && get<0>(busy.top()) == time) {
                    auto [t, w, i] = busy.top(); busy.pop();
                    free.push({w, i});
                }
            }
            auto [w, i] = free.top(); free.pop();
            ans[j] = i;
            busy.push({time + tasks[j], w, i});
        }
        return ans;
    }
};
      
import java.util.*;

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        int n = servers.length, m = tasks.length;
        PriorityQueue<int[]> free = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        PriorityQueue<long[]> busy = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : (a[1] == b[1] ? (int)a[2] - (int)b[2] : (int)a[1] - (int)b[1]));
        for (int i = 0; i < n; ++i)
            free.offer(new int[]{servers[i], i});
        int[] ans = new int[m];
        long time = 0;
        for (int j = 0; j < m; ++j) {
            time = Math.max(time, j);
            while (!busy.isEmpty() && busy.peek()[0] <= time) {
                long[] b = busy.poll();
                free.offer(new int[]{(int)b[1], (int)b[2]});
            }
            if (free.isEmpty()) {
                time = busy.peek()[0];
                while (!busy.isEmpty() && busy.peek()[0] == time) {
                    long[] b = busy.poll();
                    free.offer(new int[]{(int)b[1], (int)b[2]});
                }
            }
            int[] f = free.poll();
            ans[j] = f[1];
            busy.offer(new long[]{time + tasks[j], f[0], f[1]});
        }
        return ans;
    }
}
      
class Heap {
    constructor(compare) {
        this.data = [];
        this.compare = compare;
    }
    push(item) {
        this.data.push(item);
        this._siftUp();
    }
    pop() {
        if (this.size() === 1) return this.data.pop();
        const top = this.data[0];
        this.data[0] = this.data.pop();
        this._siftDown();
        return top;
    }
    peek() {
        return this.data[0];
    }
    size() {
        return this.data.length;
    }
    _siftUp() {
        let idx = this.data.length - 1;
        while (idx > 0) {
            let p = Math.floor((idx - 1) / 2);
            if (this.compare(this.data[idx], this.data[p]) < 0) {
                [this.data[idx], this.data[p]] = [this.data[p], this.data[idx]];
                idx = p;
            } else break;
        }
    }
    _siftDown() {
        let idx = 0, n = this.data.length;
        while (2 * idx + 1 < n) {
            let l = 2 * idx + 1, r = 2 * idx + 2, min = l;
            if (r < n && this.compare(this.data[r], this.data[l]) < 0) min = r;
            if (this.compare(this.data[min], this.data[idx]) < 0) {
                [this.data[idx], this.data[min]] = [this.data[min], this.data[idx]];
                idx = min;
            } else break;
        }
    }
}

var assignTasks = function(servers, tasks) {
    let n = servers.length, m = tasks.length;
    let free = new Heap((a, b) => a[0] - b[0] || a[1] - b[1]);
    let busy = new Heap((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
    for (let i = 0; i < n; ++i) free.push([servers[i], i]);
    let ans = Array(m), time = 0;
    for (let j = 0; j < m; ++j) {
        time = Math.max(time, j);
        while (busy.size() && busy.peek()[0] <= time) {
            let [t, w, i] = busy.pop();
            free.push([w, i]);
        }
        if (free.size() === 0) {
            time = busy.peek()[0];
            while (busy.size() && busy.peek()[0] === time) {
                let [t, w, i] = busy.pop();
                free.push([w, i]);
            }
        }
        let [w, i] = free.pop();
        ans[j] = i;
        busy.push([time + tasks[j], w, i]);
    }
    return ans;
};