You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the ith server, and tasks[j] is the time needed to process the jth 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 jth 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 == ntasks.length == m1 <= n, m <= 2 * 1051 <= servers[i], tasks[j] <= 2 * 105Problem Overview: You are given multiple servers with different weights and a list of tasks arriving each second. Each task must be assigned to the available server with the smallest weight (and smallest index if tied). If no server is free, the system waits until the next server becomes available and processes the queued tasks.
Approach 1: Simulate Time and Check Availability (O(n * m) time, O(n) space)
This method directly simulates the system timeline. At each task arrival time, iterate through all servers and pick the free one with the smallest weight and index. If all servers are busy, advance the current time to when the earliest server finishes and retry the assignment. You maintain server states (busy until time) in a simple structure and repeatedly scan to find the best candidate. The approach uses basic array operations and explicit time simulation.
The implementation is straightforward but inefficient for large inputs because each task assignment may require scanning all servers. With n servers and m tasks, worst-case time becomes O(n * m). Space complexity stays O(n) for tracking server availability.
Approach 2: Priority Queue for Servers (O((n + m) log n) time, O(n) space)
This approach uses two heap (priority queue) structures to manage server states efficiently. One min-heap stores available servers ordered by (weight, index). Another min-heap tracks busy servers ordered by their next available time. As each task arrives, first move any servers whose completion time is less than or equal to the current time from the busy heap back to the available heap.
If an available server exists, pop the best one and assign the task. If none are available, fast-forward time to the earliest finishing server, release it, and continue scheduling. Each assignment and state transition uses heap push/pop operations, keeping the process efficient. This avoids scanning all servers and ensures that selecting the optimal server always takes O(log n) time.
Recommended for interviews: The priority queue solution is the expected answer. It demonstrates strong understanding of scheduling systems, heaps, and event simulation. Starting with the brute-force simulation helps show reasoning, but interviewers typically look for the optimized heap-based scheduler with O((n + m) log n) complexity.
In this approach, use two priority queues: one to manage the free servers based on weight and index, and another to track busy servers (when they will be free). At each timestamp, assign available servers to tasks in the queue.
The solution uses two priority queues to manage available and busy servers effectively. Free servers are sorted by weight and index, while busy servers are tracked by the time they will become free.
Time Complexity: O((n + m) log n), where n is the number of servers and m is the number of tasks, due to the heap operations.
Space Complexity: O(n + m) to store the priority queues and the result array.
Simulate the process by checking each time point for available servers. If a server becomes free, handle tasks in the order of their arrival and manage availability accordingly.
This C++ solution simulates task assignment over time using two priority queues for free and busy servers, ensuring tasks are processed in arrival order via a separate queue.
Time Complexity: O((n + m) log n), owing to the priority queue handling of free and busy servers.
Space Complexity: O(n + m), accounting for server management and result tracking.
We use a min-heap idle to maintain all idle servers, where each element is a tuple (x, i) representing the i-th server with weight x. We use another min-heap busy to maintain all busy servers, where each element is a tuple (w, s, i) representing the i-th server that will be idle at time w with weight s. Initially, we add all servers to idle.
Next, we iterate through all tasks. For the j-th task, we first remove all servers from busy that will be idle at or before time j and add them to idle. Then we take the server with the smallest weight from idle, add it to busy, and assign it to the j-th task. If idle is empty, we take the server with the earliest idle time from busy, add it to busy, and assign it to the j-th task.
After iterating through all tasks, we obtain the answer array ans.
The time complexity is O((n + m) log n), where n is the number of servers and m is the number of tasks. The space complexity is O(n). Here, n and m are the number of servers and tasks, respectively.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Priority Queue for Servers | Time Complexity: O((n + m) log n), where n is the number of servers and m is the number of tasks, due to the heap operations. |
| Simulate Time and Check Availability | Time Complexity: O((n + m) log n), owing to the priority queue handling of free and busy servers. |
| Priority Queue (Min-Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Time and Check Availability | O(n * m) | O(n) | Useful for understanding the scheduling process or when constraints are small |
| Priority Queue for Servers | O((n + m) log n) | O(n) | Best general solution for large inputs and expected approach in interviews |
Process Tasks Using Servers - Leetcode 1882 - Python • NeetCode • 18,694 views views
Watch 7 more video solutions →Practice Process Tasks Using Servers with our built-in code editor and test cases.
Practice on FleetCode