Process Tasks Using Servers

Med

#1718Time: 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)`).3 companies

Data structures

Array Heap (Priority Queue)

Companies

PayPal Lyft X

Prompt

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 j^th task is inserted into the queue (starting with the 0^th 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 * 10⁵
1 <= servers[i], tasks[j] <= 2 * 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1// NOTE: This implementation is for conceptual understanding and will Time Limit Exceed.2class Solution {3    public int[] assignTasks(int[] servers, int[] tasks) {4        int n = servers.length;5        int m = tasks.length;6        int[] ans = new int[m];7        long[] serverFreeTime = new long[n];8        Queue<Integer> taskQueue = new LinkedList<>();9        int tasksAssigned = 0;10        int taskIdx = 0;11        long time = 0;12 13        while (tasksAssigned < m) {14            // Add newly arrived tasks to the queue15            while (taskIdx < m && taskIdx <= time) {16                taskQueue.offer(taskIdx++);17            }18 19            // Assign tasks from queue to free servers20            while (!taskQueue.isEmpty()) {21                int bestServer = -1;22                // Find the best free server (O(n) scan)23                for (int i = 0; i < n; i++) {24                    if (serverFreeTime[i] <= time) {25                        if (bestServer == -1 || 26                            servers[i] < servers[bestServer] ||27                            (servers[i] == servers[bestServer] && i < bestServer)) {28                            bestServer = i;29                        }30                    }31                }32 33                if (bestServer != -1) {34                    int currentTask = taskQueue.poll();35                    ans[currentTask] = bestServer;36                    serverFreeTime[bestServer] = time + tasks[currentTask];37                    tasksAssigned++;38                } else {39                    // No free servers, break and advance time40                    break;41                }42            }43            44            // Advance time45            if (taskQueue.isEmpty() && taskIdx < m) {46                // Jump to next task arrival if no tasks are waiting47                time = Math.max(time + 1, taskIdx);48            } else {49                time++;50            }51        }52        return ans;53    }54}

Complexity

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)`).

Trade-offs

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.

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.

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.

Walkthrough

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.

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.
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.
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.

1import java.util.*;2 3class Solution {4    public int[] assignTasks(int[] servers, int[] tasks) {5        // Min-heap for available servers: {weight, index}6        PriorityQueue<int[]> availableServers = new PriorityQueue<>((a, b) -> 7            a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);8        for (int i = 0; i < servers.length; i++) {9            availableServers.offer(new int[]{servers[i], i});10        }11 12        // Min-heap for busy servers: {freeTime, index}13        PriorityQueue<long[]> busyServers = new PriorityQueue<>((a, b) -> 14            Long.compare(a[0], b[0]));15 16        Queue<Integer> taskQueue = new LinkedList<>();17        int[] ans = new int[tasks.length];18        long time = 0;19        int taskIndex = 0;20 21        while (taskIndex < tasks.length || !taskQueue.isEmpty()) {22            // Add all tasks that have arrived by the current 'time' to the waiting queue23            while (taskIndex < tasks.length && taskIndex <= time) {24                taskQueue.offer(taskIndex++);25            }26 27            // Free up servers that are done by the current 'time'28            while (!busyServers.isEmpty() && busyServers.peek()[0] <= time) {29                long[] serverInfo = busyServers.poll();30                int serverIdx = (int) serverInfo[1];31                availableServers.offer(new int[]{servers[serverIdx], serverIdx});32            }33 34            // Assign tasks from the queue to any available free servers35            while (!taskQueue.isEmpty() && !availableServers.isEmpty()) {36                int currentTask = taskQueue.poll();37                int[] server = availableServers.poll();38                ans[currentTask] = server[1];39                busyServers.offer(new long[]{time + tasks[currentTask], server[1]});40            }41 42            // If there are still tasks to be processed, advance time to the next event43            if (taskIndex < tasks.length || !taskQueue.isEmpty()) {44                if (availableServers.isEmpty()) {45                    // If no servers are free, jump time to when the next server becomes free46                    time = busyServers.peek()[0];47                } else {48                    // If servers are free but no tasks are waiting, jump to the next task's arrival49                    time = taskIndex;50                }51            }52        }53        return ans;54    }55}

Complexity

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)`).

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] assignTasks(int[] servers, int[] tasks) {4    int m = tasks.length, n = servers.length;5    PriorityQueue<int[]> idle =6        new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);7    PriorityQueue<int[]> busy = new PriorityQueue<>((a, b)->{8      if (a[0] == b[0]) {9        return a[1] == b[1] ? a[2] - b[2] : a[1] - b[1];10      }11      return a[0] - b[0];12    });13    for (int i = 0; i < n; ++i) {14      idle.offer(new int[]{servers[i], i});15    }16    int[] res = new int[m];17    int j = 0;18    for (int start = 0; start < m; ++start) {19      int cost = tasks[start];20      while (!busy.isEmpty() && busy.peek()[0] <= start) {21        int[] item = busy.poll();22        idle.offer(new int[]{item[1], item[2]});23      }24      if (!idle.isEmpty()) {25        int[] item = idle.poll();26        res[j++] = item[1];27        busy.offer(new int[]{start + cost, item[0], item[1]});28      } else {29        int[] item = busy.poll();30        res[j++] = item[2];31        busy.offer(new int[]{item[0] + cost, item[1], item[2]});32      }33    }34    return res;35  }36}

1class Solution:2    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

1class Solution {2public:3  vector<int> assignTasks(vector<int> &servers, vector<int> &tasks) {4    using pii = pair<int, int>;5    using arr3 = array<int, 3>;6    priority_queue<pii, vector<pii>, greater<pii>> idle;7    priority_queue<arr3, vector<arr3>, greater<arr3>> busy;8    for (int i = 0; i < servers.size(); ++i) {9      idle.push({servers[i], i});10    }11    int m = tasks.size();12    vector<int> ans(m);13    for (int j = 0; j < m; ++j) {14      int t = tasks[j];15      while (!busy.empty() && busy.top()[0] <= j) {16        auto [_, s, i] = busy.top();17        busy.pop();18        idle.push({s, i});19      }20      if (!idle.empty()) {21        auto [s, i] = idle.top();22        idle.pop();23        ans[j] = i;24        busy.push({j + t, s, i});25      } else {26        auto [w, s, i] = busy.top();27        busy.pop();28        ans[j] = i;29        busy.push({w + t, s, i});30      }31    }32    return ans;33  }34};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem