Server Task Assignment

MediumHeap / Priority Queue

Problem

A cluster has servers with weights[i] (lower is cheaper to use). Task j arrives at time j and needs tasks[j] time units on one server. Tasks are assigned strictly in arrival order, each one as early as possible:

If one or more servers are free when a task is assigned, it goes to the free server with the smallest weight, breaking ties by the smallest index. If none is free, the task waits until the earliest moment a server frees up and then picks among the servers free at that moment by the same rule. A server busy until time t is free again at time t. A task can never be assigned before the task ahead of it.

Return an array where entry j is the index of the server that runs task j.

Example 1

Input:
weights = [3, 3, 2], tasks = [1, 2, 3, 2, 1, 2]
Output:
[2, 2, 0, 2, 1, 2]

t=0: server 2 (weight 2) takes task 0 until 1. t=1: server 2 again, until 3. t=2: server 0 (weight 3, smaller index), until 5. t=3: server 2, until 5. t=4: server 1, until 5. t=5: all free → server 2.

Example 2

Input:
weights = [1], tasks = [3, 1, 2]
Output:
[0, 0, 0]

Task 1 waits until time 3, task 2 until time 4.

Constraints

  • 1 ≤ weights.length, tasks.length ≤ 2·10^5
  • 1 ≤ weights[i], tasks[j] ≤ 2·10^5

Hint

Show the first hint

Servers are in one of two states, free or busy, and each state needs a different 'best' server.

Walkthrough

How to approach it

01Clarify before coding

  • Can a later task overtake a waiting one? No, assignment is in arrival order.
  • Is a server busy until t available at t? Yes.
  • When several servers free up at the same moment and a task is waiting, which wins? The usual rule: smallest weight, then index.

02Brute force

For each task, scan all servers for free ones (or the earliest to free) and pick the best by (weight, index).

Cost: O(m · n) = 4·10^10 for the limits.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.