Process Tasks Using Servers
Medium · Heap & Counting · Array · Heap (Priority Queue) · Simulation
Problem
You are given two arrays: servers, where servers[i] is the weight of server i, and tasks, where tasks[j] is how many seconds task j takes. Task j joins a queue at second j (starting from 0).
Whenever there is a free server and a waiting task, the task at the front of the queue goes to the free server with the smallest weight, breaking ties by the smallest index. If no server is free, tasks wait until one frees up; if several tasks can be assigned at the same moment, they are assigned in queue order, each by the same rule.
A server given task j at second t becomes free again at second t + tasks[j]. Return an array ans where ans[j] is the index of the server that runs task j.
Examples
Input: servers = [3,3,2], tasks = [1,2,3,2,1,2] Output: [2,2,0,2,1,2]
Server 2 is the lightest and takes tasks 0, 1 and 3, each time it is free. Task 2 goes to server 0 and task 4 to server 1 (same weight, larger index). At second 5 every server is free again, and the lightest, server 2, takes task 5.
Input: servers = [5,1,4], tasks = [2,1,2,4,5,2,1] Output: [1,2,1,2,1,0,2]
At second 6 every server is busy, so task 6 waits until second 7, when servers 0 and 2 both free up; the lighter one, server 2, takes it.
Input: servers = [5], tasks = [2,2,1] Output: [0,0,0]
With one server every task runs on server 0, each waiting for the one before it.
Constraints
- servers.length == n
- tasks.length == m
- 1 <= n, m <= 2 · 10^5
- 1 <= servers[i], tasks[j] <= 2 · 10^5
Approaches
- Baseline: scan every server for each task — time O(n · m), space O(n + m)
Follow-up
If a task could not wait (it is dropped when every server is busy) and servers were chosen round-robin from the task's own index, you would need an ordered set of free indices instead of a weight heap. Times here can reach 2 · 10^5 · 2 · 10^5 = 4 · 10^10 seconds, so in Java, C++ and Go the clock must be a 64-bit integer.
Related problems
Start free on Cariara · Coding problems · System design studio
