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

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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.

Solution

Method 1 – Using Min Heaps

Intuition

To efficiently assign tasks to servers based on their weights and availability, we can use two min-heaps: one for free servers and one for busy servers. This allows us to always select the best available server for each task and to quickly update server availability as tasks are processed.

Approach

  1. Free Servers Heap:

    • Maintain a min-heap of free servers, ordered by (weight, index). This ensures that the server with the smallest weight (and smallest index in case of a tie) is always chosen first.

  2. Used Servers Heap:

    • Maintain a min-heap of busy servers, ordered by (availableTime, weight, index). This allows us to efficiently determine when servers become available.

  3. Task Assignment:

    • For each task (arriving at time i), first move any servers from the used heap to the free heap if they have become available by time i.
    • If there are free servers, assign the task to the best available server and update its next available time.
    • If no servers are free, wait for the soonest available server, assign the task as soon as it is free, and update its next available time.

  4. Result:

    • Track the index of the server assigned to each task in the result array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
	vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
		using T = tuple<long long, int, int>; // (availableTime, weight, index)
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> free;
		priority_queue<T, vector<T>, greater<>> busy;
		int n = servers.size(), m = tasks.size();
		for (int i = 0; i < n; ++i) free.emplace(servers[i], i);
		vector<int> ans(m);
		long long time = 0;
		for (int i = 0; i < m; ++i) {
			time = max(time, (long long)i);
			while (!busy.empty() && get<0>(busy.top()) <= time) {
				auto [avail, w, idx] = busy.top(); busy.pop();
				free.emplace(w, idx);
			}
			if (free.empty()) {
				time = get<0>(busy.top());
				while (!busy.empty() && get<0>(busy.top()) == time) {
					auto [avail, w, idx] = busy.top(); busy.pop();
					free.emplace(w, idx);
				}
			}
			auto [w, idx] = free.top(); free.pop();
			ans[i] = idx;
			busy.emplace(time + tasks[i], w, idx);
		}
		return ans;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import (
	"container/heap"
)
type Server struct{weight, index, avail int}
type FreeHeap []Server
func (h FreeHeap) Len() int { return len(h) }
func (h FreeHeap) Less(i, j int) bool {
	if h[i].weight == h[j].weight { return h[i].index < h[j].index }
	return h[i].weight < h[j].weight
}
func (h FreeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *FreeHeap) Push(x interface{}) { *h = append(*h, x.(Server)) }
func (h *FreeHeap) Pop() interface{} { n := len(*h); x := (*h)[n-1]; *h = (*h)[:n-1]; return x }
type BusyHeap []Server
func (h BusyHeap) Len() int { return len(h) }
func (h BusyHeap) Less(i, j int) bool {
	if h[i].avail == h[j].avail {
		if h[i].weight == h[j].weight { return h[i].index < h[j].index }
		return h[i].weight < h[j].weight
	}
	return h[i].avail < h[j].avail
}
func (h BusyHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *BusyHeap) Push(x interface{}) { *h = append(*h, x.(Server)) }
func (h *BusyHeap) Pop() interface{} { n := len(*h); x := (*h)[n-1]; *h = (*h)[:n-1]; return x }
func assignTasks(servers []int, tasks []int) []int {
	n, m := len(servers), len(tasks)
	free := &FreeHeap{}
	busy := &BusyHeap{}
	for i, w := range servers { heap.Push(free, Server{w, i, 0}) }
	ans := make([]int, m)
	time := 0
	for i, t := range tasks {
		if time < i { time = i }
		for busy.Len() > 0 && (*busy)[0].avail <= time {
			s := heap.Pop(busy).(Server)
			heap.Push(free, Server{s.weight, s.index, 0})
		}
		if free.Len() == 0 {
			time = (*busy)[0].avail
			for busy.Len() > 0 && (*busy)[0].avail == time {
				s := heap.Pop(busy).(Server)
				heap.Push(free, Server{s.weight, s.index, 0})
			}
		}
		s := heap.Pop(free).(Server)
		ans[i] = s.index
		heap.Push(busy, Server{s.weight, s.index, time + t})
	}
	return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.*;
class Solution {
	public int[] assignTasks(int[] servers, int[] tasks) {
		PriorityQueue<int[]> free = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
		PriorityQueue<int[]> busy = new PriorityQueue<>((a, b) -> a[2] != b[2] ? a[2] - b[2] : (a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]));
		int n = servers.length, m = tasks.length;
		for (int i = 0; i < n; i++) free.offer(new int[]{servers[i], i, 0});
		int[] ans = new int[m];
		int time = 0;
		for (int i = 0; i < m; i++) {
			time = Math.max(time, i);
			while (!busy.isEmpty() && busy.peek()[2] <= time) free.offer(busy.poll());
			if (free.isEmpty()) {
				time = busy.peek()[2];
				while (!busy.isEmpty() && busy.peek()[2] == time) free.offer(busy.poll());
			}
			int[] cur = free.poll();
			ans[i] = cur[1];
			cur[2] = time + tasks[i];
			busy.offer(cur);
		}
		return ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import java.util.PriorityQueue
class Solution {
	fun assignTasks(servers: IntArray, tasks: IntArray): IntArray {
		val free = PriorityQueue(compareBy<Pair<Int, Int>>({ it.first }, { it.second }))
		val busy = PriorityQueue(compareBy<Triple<Int, Int, Int>>({ it.third }, { it.first }, { it.second }))
		servers.forEachIndexed { i, w -> free.add(w to i) }
		val ans = IntArray(tasks.size)
		var time = 0
		for (i in tasks.indices) {
			time = maxOf(time, i)
			while (busy.isNotEmpty() && busy.peek().third <= time) {
				val (w, idx, _) = busy.poll()
				free.add(w to idx)
			}
			if (free.isEmpty()) {
				time = busy.peek().third
				while (busy.isNotEmpty() && busy.peek().third == time) {
					val (w, idx, _) = busy.poll()
					free.add(w to idx)
				}
			}
			val (w, idx) = free.poll()
			ans[i] = idx
			busy.add(Triple(w, idx, time + tasks[i]))
		}
		return ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import heapq
class Solution:
	def assignTasks(self, servers, tasks):
		n, m = len(servers), len(tasks)
		free = [(w, i) for i, w in enumerate(servers)]
		heapq.heapify(free)
		busy = []  # (availableTime, weight, index)
		ans = [0] * m
		time = 0
		for i, t in enumerate(tasks):
			time = max(time, i)
			while busy and busy[0][0] <= time:
				_, w, idx = heapq.heappop(busy)
				heapq.heappush(free, (w, idx))
			if not free:
				time = busy[0][0]
				while busy and busy[0][0] == time:
					_, w, idx = heapq.heappop(busy)
					heapq.heappush(free, (w, idx))
			w, idx = heapq.heappop(free)
			ans[i] = idx
			heapq.heappush(busy, (time + t, w, idx))
		return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
	pub fn assign_tasks(servers: Vec<i32>, tasks: Vec<i32>) -> Vec<i32> {
		let mut free = BinaryHeap::new(); // min-heap by (weight, index)
		let mut busy = BinaryHeap::new(); // min-heap by (available_time, weight, index)
		let n = servers.len();
		for (i, &w) in servers.iter().enumerate() {
			free.push(Reverse((w, i)));
		}
		let mut ans = vec![0; tasks.len()];
		let mut time = 0;
		for (i, &t) in tasks.iter().enumerate() {
			time = time.max(i);
			while let Some(&Reverse((avail, w, idx))) = busy.peek() {
				if avail > time as i32 { break; }
				busy.pop();
				free.push(Reverse((w, idx)));
			}
			if free.is_empty() {
				if let Some(&Reverse((avail, _, _))) = busy.peek() {
					time = avail as usize;
				}
				while let Some(&Reverse((avail, w, idx))) = busy.peek() {
					if avail as usize != time { break; }
					busy.pop();
					free.push(Reverse((w, idx)));
				}
			}
			let Reverse((w, idx)) = free.pop().unwrap();
			ans[i] = idx as i32;
			busy.push(Reverse((time as i32 + t, w, idx)));
		}
		ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

function assignTasks(servers: number[], tasks: number[]): number[] {
	const n = servers.length, m = tasks.length;
	const free: [number, number][] = servers.map((w, i) => [w, i]);
	free.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
	const busy: [number, number, number][] = [];
	const ans: number[] = Array(m);
	let time = 0, freePtr = 0;
	for (let i = 0; i < m; i++) {
		time = Math.max(time, i);
		while (busy.length && busy[0][0] <= time) {
			const [avail, w, idx] = busy.shift()!;
			let pos = free.findIndex(([fw, fi]) => fw > w || (fw === w && fi > idx));
			if (pos === -1) pos = free.length;
			free.splice(pos, 0, [w, idx]);
		}
		if (!free.length) {
			time = busy[0][0];
			while (busy.length && busy[0][0] === time) {
				const [avail, w, idx] = busy.shift()!;
				let pos = free.findIndex(([fw, fi]) => fw > w || (fw === w && fi > idx));
				if (pos === -1) pos = free.length;
				free.splice(pos, 0, [w, idx]);
			}
		}
		const [w, idx] = free.shift()!;
		ans[i] = idx;
		let pos = busy.findIndex(([avail]) => avail > time + tasks[i]);
		if (pos === -1) pos = busy.length;
		busy.splice(pos, 0, [time + tasks[i], w, idx]);
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O((N + M) * log N), where N is the number of servers and M is the number of tasks. Each task assignment and server release involves heap operations.
  • 🧺 Space complexity: O(N + M) for the heaps and result array.