# Process Tasks Using Servers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/process-tasks-using-servers)
Canonical: https://scaleengineer.com/dsa/problems/process-tasks-using-servers
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [Lyft](https://scaleengineer.com/companies/lyft), [X](https://scaleengineer.com/companies/x)
---
## Problem
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 `jth` task is **inserted** into the queue (starting with the `0th` 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**, and in case of 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 and immediately assign the next task. If multiple servers become free at the same time, then multiple tasks from the queue will be assigned **in order of insertion** following the weight and index priorities above.

A server that is assigned task `j` at second `t` will be free again at second `t + tasks[j]`.

Build an array `ans`​​​​ of length `m`, where `ans[j]` is the **index** of the server the `j​​​​​​th` task will be assigned to.

Return _the array_ `ans`​​​​.

**Example 1:**

**Input:** servers = [3,3,2], tasks = [1,2,3,2,1,2]
**Output:** [2,2,0,2,1,2]
**Explanation:** Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 2 until second 1.
- At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
- At second 2, task 2 is added and processed using server 0 until second 5.
- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
- At second 4, task 4 is added and processed using server 1 until second 5.
- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.

**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:** Events in chronological order go as follows: 
- At second 0, task 0 is added and processed using server 1 until second 2.
- At second 1, task 1 is added and processed using server 4 until second 2.
- At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4. 
- At second 3, task 3 is added and processed using server 4 until second 7.
- At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9. 
- At second 5, task 5 is added and processed using server 3 until second 7.
- At second 6, task 6 is added and processed using server 2 until second 7.

**Constraints:**

* `servers.length == n`
* `tasks.length == m`
* `1 <= n, m <= 2 * 105`
* `1 <= servers[i], tasks[j] <= 2 * 105`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem statement by advancing time second by second. It maintains an array to track when each server becomes free and a queue for tasks that have arrived but are waiting for a server. At each time step, it checks for new task arrivals and then attempts to assign tasks from the queue to any available servers. The best available server is found by performing a linear scan through all servers.
**Time:** O(T_max * n), where `T_max` is the completion time of the last task. In the worst case, `T_max` can be very large (e.g., `m + m * max_task_duration`), and for each time step, we might scan all `n` servers. This is highly inefficient and will not pass the given constraints. · **Space:** O(n + m) to store the server free times (`O(n)`) and the task queue (`O(m)`).
**Pros:** Conceptually simple and follows the problem description literally.; Easy to implement without complex data structures.
**Cons:** Extremely inefficient due to the second-by-second time progression.; The linear scan `O(n)` to find the best server at each assignment step is a major bottleneck.; Guaranteed to receive a 'Time Limit Exceeded' (TLE) verdict on platforms like LeetCode for the given constraints.
### Explanation
The brute-force method involves a step-by-step simulation of time. We use a variable `time`, which starts at 0 and increments, representing the passage of seconds. We maintain an array, `serverFreeTime`, to keep track of the moment each server finishes its current task and becomes available again. A simple queue, `taskQueue`, holds the indices of tasks that have arrived but couldn't be assigned immediately.

The main loop of the simulation continues as long as not all tasks have been assigned. In each iteration, representing a single second, we first add any newly arrived tasks to the `taskQueue`. Then, we check if any tasks can be assigned. To do this, we repeatedly scan through all `n` servers to find the best available one (minimum weight, then minimum index). If a suitable free server is found, we assign it the task from the front of the `taskQueue`, update the server's free time, and record the assignment. If no servers are free, we must wait, so we simply advance the `time` to the next second. This process continues until all `m` tasks are assigned.

```java
// NOTE: This implementation is for conceptual understanding and will Time Limit Exceed.
class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        int n = servers.length;
        int m = tasks.length;
        int[] ans = new int[m];
        long[] serverFreeTime = new long[n];
        Queue<Integer> taskQueue = new LinkedList<>();
        int tasksAssigned = 0;
        int taskIdx = 0;
        long time = 0;

        while (tasksAssigned < m) {
            // Add newly arrived tasks to the queue
            while (taskIdx < m && taskIdx <= time) {
                taskQueue.offer(taskIdx++);
            }

            // Assign tasks from queue to free servers
            while (!taskQueue.isEmpty()) {
                int bestServer = -1;
                // Find the best free server (O(n) scan)
                for (int i = 0; i < n; i++) {
                    if (serverFreeTime[i] <= time) {
                        if (bestServer == -1 || 
                            servers[i] < servers[bestServer] ||
                            (servers[i] == servers[bestServer] && i < bestServer)) {
                            bestServer = i;
                        }
                    }
                }

                if (bestServer != -1) {
                    int currentTask = taskQueue.poll();
                    ans[currentTask] = bestServer;
                    serverFreeTime[bestServer] = time + tasks[currentTask];
                    tasksAssigned++;
                } else {
                    // No free servers, break and advance time
                    break;
                }
            }
            
            // Advance time
            if (taskQueue.isEmpty() && taskIdx < m) {
                // Jump to next task arrival if no tasks are waiting
                time = Math.max(time + 1, taskIdx);
            } else {
                time++;
            }
        }
        return ans;
    }
}
```
### Algorithm
*   Initialize a `serverFreeTime` array of size `n` to all zeros, where `serverFreeTime[i]` stores the time server `i` becomes free.
*   Initialize an empty FIFO `taskQueue` to store indices of waiting tasks.
*   Initialize a `time` variable to 0 and a counter for assigned tasks.
*   Start a loop that continues until all `m` tasks are assigned.
*   Inside the loop, advance `time`.
    1.  **Task Arrival:** Add any tasks that arrive at or before the current `time` to the `taskQueue`.
    2.  **Task Assignment:** While the `taskQueue` is not empty, try to assign tasks.
    3.  To assign a task, perform a linear scan through all `n` servers.
    4.  A server `i` is considered free if `serverFreeTime[i] <= time`.
    5.  Find the best free server by keeping track of the one with the minimum weight, using the index as a tiebreaker.
    6.  If a free server is found, dequeue a task, assign it to the server, update `ans[task_index]`, and set the server's new `serverFreeTime` to `time + task_duration`.
    7.  If no free server is found, break the assignment inner loop and advance to the next time step.
*   The simulation time is advanced by one second in each step, or jumped to the next task arrival time if the queue is empty to avoid unnecessary iterations.

## Dual Priority Queue (Min-Heap) Simulation
This optimal approach uses an event-driven simulation model, which is significantly more efficient. Instead of advancing time second-by-second, we jump directly to the next important event, which is either a new task arriving or a server becoming free. This is managed using two priority queues (min-heaps): one to efficiently find the best available server and another to efficiently find the next server that will become free.
**Time:** O((n + m) log n). Initializing the `availableServers` heap takes `O(n log n)`. Each of the `m` tasks results in a constant number of heap operations (poll from available, offer to busy, and later poll from busy, offer to available), each taking `O(log n)`. Thus, the total time is dominated by these heap operations. · **Space:** O(n + m). The two priority queues can store up to `n` servers in total (`O(n)`), and the task queue can, in the worst-case, store all `m` tasks (`O(m)`).
**Pros:** Highly efficient due to the event-driven simulation model.; Logarithmic time complexity for server management operations, making it suitable for large inputs.; This is the optimal solution for the given constraints.
**Cons:** More complex to implement compared to the brute-force approach.; Requires careful management of the simulation time and multiple data structures to ensure correctness.
### Explanation
To solve this problem efficiently, we avoid simulating every single second. We use two priority queues to manage the state of the servers and a regular queue for waiting tasks.

1.  **`availableServers` (Min-Heap):** This priority queue stores the servers that are currently free. Each element is an array `[weight, index]`. The heap is ordered first by `weight` and then by `index` in case of a tie. This allows us to retrieve the best available server in `O(log n)` time.

2.  **`busyServers` (Min-Heap):** This priority queue stores servers that are currently processing tasks. Each element is an array `[freeTime, index]`. The heap is ordered by `freeTime`, so we can quickly find which server will finish its task earliest in `O(log n)` time.

3.  **`taskQueue` (FIFO Queue):** This queue stores the indices of tasks that have arrived but are waiting for a server to become free. It maintains the order of arrival.

The simulation proceeds by jumping between event times. The main loop continues as long as there are tasks to process. In each step, we update the current `time`. We move any servers from `busyServers` to `availableServers` if their tasks are complete by the current `time`. We also add any newly arrived tasks to the `taskQueue`. Then, we assign as many waiting tasks as possible to available servers. The key to efficiency is how we advance `time`. If there are no free servers, we jump `time` forward to the moment the next busy server becomes free. If there are free servers, we can advance `time` to the arrival of the next task.

```java
import java.util.*;

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        // Min-heap for available servers: {weight, index}
        PriorityQueue<int[]> availableServers = new PriorityQueue<>((a, b) -> 
            a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        for (int i = 0; i < servers.length; i++) {
            availableServers.offer(new int[]{servers[i], i});
        }

        // Min-heap for busy servers: {freeTime, index}
        PriorityQueue<long[]> busyServers = new PriorityQueue<>((a, b) -> 
            Long.compare(a[0], b[0]));

        Queue<Integer> taskQueue = new LinkedList<>();
        int[] ans = new int[tasks.length];
        long time = 0;
        int taskIndex = 0;

        while (taskIndex < tasks.length || !taskQueue.isEmpty()) {
            // Add all tasks that have arrived by the current 'time' to the waiting queue
            while (taskIndex < tasks.length && taskIndex <= time) {
                taskQueue.offer(taskIndex++);
            }

            // Free up servers that are done by the current 'time'
            while (!busyServers.isEmpty() && busyServers.peek()[0] <= time) {
                long[] serverInfo = busyServers.poll();
                int serverIdx = (int) serverInfo[1];
                availableServers.offer(new int[]{servers[serverIdx], serverIdx});
            }

            // Assign tasks from the queue to any available free servers
            while (!taskQueue.isEmpty() && !availableServers.isEmpty()) {
                int currentTask = taskQueue.poll();
                int[] server = availableServers.poll();
                ans[currentTask] = server[1];
                busyServers.offer(new long[]{time + tasks[currentTask], server[1]});
            }

            // If there are still tasks to be processed, advance time to the next event
            if (taskIndex < tasks.length || !taskQueue.isEmpty()) {
                if (availableServers.isEmpty()) {
                    // If no servers are free, jump time to when the next server becomes free
                    time = busyServers.peek()[0];
                } else {
                    // If servers are free but no tasks are waiting, jump to the next task's arrival
                    time = taskIndex;
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
*   Initialize two priority queues (min-heaps):
    1.  `availableServers`: Stores `(weight, index)` for free servers. It's a min-heap ordered by weight, then index.
    2.  `busyServers`: Stores `(freeTime, index)` for busy servers. It's a min-heap ordered by `freeTime`.
*   Initialize a standard FIFO `taskQueue` for waiting tasks.
*   Populate `availableServers` with all `n` servers initially.
*   Initialize `time = 0` and `taskIndex = 0`.
*   The main simulation loop continues as long as there are tasks to be processed (either not yet arrived or waiting in the queue).
*   Inside the loop:
    1.  **Free Up Servers:** Move any servers from `busyServers` to `availableServers` if their `freeTime` is less than or equal to the current `time`.
    2.  **Queue Arriving Tasks:** Add all tasks whose arrival time (`taskIndex`) is less than or equal to `time` into the `taskQueue`.
    3.  **Assign Tasks:** As long as both `taskQueue` and `availableServers` are not empty, dequeue a task, poll the best server from `availableServers`, record the assignment, and add the server to `busyServers` with its new `freeTime` (`time + task_duration`).
    4.  **Advance Time:** This is the crucial step. Instead of incrementing by one, we jump to the next significant event.
        *   If `availableServers` is empty (and there are tasks waiting or yet to arrive), we must wait. The next event is the earliest time a server becomes free. We set `time = busyServers.peek().freeTime`.
        *   Otherwise (if `availableServers` has servers), we can process the next incoming task at its arrival time. We set `time = taskIndex`.

# Solutions
### Java

```java
class Solution {
public
  int[] assignTasks(int[] servers, int[] tasks) {
    int m = tasks.length, n = servers.length;
    PriorityQueue<int[]> idle =
        new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    PriorityQueue<int[]> busy = new PriorityQueue<>((a, b)->{
      if (a[0] == b[0]) {
        return a[1] == b[1] ? a[2] - b[2] : a[1] - b[1];
      }
      return a[0] - b[0];
    });
    for (int i = 0; i < n; ++i) {
      idle.offer(new int[]{servers[i], i});
    }
    int[] res = new int[m];
    int j = 0;
    for (int start = 0; start < m; ++start) {
      int cost = tasks[start];
      while (!busy.isEmpty() && busy.peek()[0] <= start) {
        int[] item = busy.poll();
        idle.offer(new int[]{item[1], item[2]});
      }
      if (!idle.isEmpty()) {
        int[] item = idle.poll();
        res[j++] = item[1];
        busy.offer(new int[]{start + cost, item[0], item[1]});
      } else {
        int[] item = busy.poll();
        res[j++] = item[2];
        busy.offer(new int[]{item[0] + cost, item[1], item[2]});
      }
    }
    return res;
  }
}

```

### Python

```python
class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]: idle, busy = [], [] for i, weight in enumerate(servers): heappush(idle, (weight, i)) res = [] for start, cost in enumerate(tasks): while busy and busy[0][0] <= start: _, s, i = heappop(busy) heappush(idle, (s, i)) if idle: s, i = heappop(idle) heappush(busy, (start + cost, s, i)) else: t, s, i = heappop(busy) heappush(busy, (t + cost, s, i)) res . append(i) return res

```

### CPP

```cpp
class Solution {
public:
  vector<int> assignTasks(vector<int> &servers, vector<int> &tasks) {
    using pii = pair<int, int>;
    using arr3 = array<int, 3>;
    priority_queue<pii, vector<pii>, greater<pii>> idle;
    priority_queue<arr3, vector<arr3>, greater<arr3>> busy;
    for (int i = 0; i < servers.size(); ++i) {
      idle.push({servers[i], i});
    }
    int m = tasks.size();
    vector<int> ans(m);
    for (int j = 0; j < m; ++j) {
      int t = tasks[j];
      while (!busy.empty() && busy.top()[0] <= j) {
        auto [_, s, i] = busy.top();
        busy.pop();
        idle.push({s, i});
      }
      if (!idle.empty()) {
        auto [s, i] = idle.top();
        idle.pop();
        ans[j] = i;
        busy.push({j + t, s, i});
      } else {
        auto [w, s, i] = busy.top();
        busy.pop();
        ans[j] = i;
        busy.push({w + t, s, i});
      }
    }
    return ans;
  }
};

```