1882. Process Tasks Using Servers
- Array
- Heap (Priority Queue)
TIME
O((n + m) log n)
SPACE
O(n + m)
Intuition
At any moment, two questions need fast answers: which idle server has the smallest (weight, index), and when does the next busy server become free. Each is a heap. The queue itself never needs storing, because tasks are assigned strictly in order. Task j starts at whichever is later: its arrival second j, or the start time of task j - 1.
Approach
- Put every server in
free, keyed by(weight, index).busystarts empty and is keyed by(free time, index). - Keep a clock
t = 0. For each taskj:t = max(t, j);- move every server in
busywhose free time is<= tintofree; - if
freeis still empty, jumptto the smallest free time inbusyand move every server freeing at that second; - pop the best server from
free, record its index, and push it tobusywith free timet + tasks[j].
- Pack each key into a single integer (
major * 2^18 + index, since indices are below2^18) so the heaps compare plain numbers.
Complexity
- Time: O((n + m) log n): each task does one pop and one push, and each release is paid for by an earlier push
- Space: O(n + m) for the heaps and the answer
Edge Cases
- A queued task starts late: if task
j - 1waited until secondT > j, taskjstarts atTtoo. Usingjas its start would make its server look free too early - Several servers free at the same second: all of them are released before choosing, so weight and index decide the order, not release order
- A server freeing exactly at second
tis available att(<=, not<) - Equal weights: the lower index wins, which the packed key handles
- One server: every task waits for it
- Free times reach about
2 * 10^5 + 2 * 10^5 * 2 * 10^5 = 4 * 10^10, and after packing about10^16, so Java useslong
Code
import heapq
class Solution:
def assignTasks(self, servers: list[int], tasks: list[int]) -> list[int]:
"""
1882. Process Tasks Using Servers
Time: O((n + m) log n)
Space: O(n + m)
"""
# Keys pack (major, index) into one int: indices are below 2^18.
SHIFT = 18
MASK = (1 << SHIFT) - 1
free = [(w << SHIFT) | i for i, w in enumerate(servers)] # (weight, index)
heapq.heapify(free)
busy = [] # (free time, index)
ans = []
t = 0
for j, duration in enumerate(tasks):
# Task j starts no earlier than it arrives or than task j - 1 started.
t = max(t, j)
if not free:
t = max(t, busy[0] >> SHIFT)
while busy and busy[0] >> SHIFT <= t:
i = heapq.heappop(busy) & MASK
heapq.heappush(free, (servers[i] << SHIFT) | i)
i = heapq.heappop(free) & MASK
ans.append(i)
heapq.heappush(busy, ((t + duration) << SHIFT) | i)
return ansimport java.util.*;
/**
* 1882. Process Tasks Using Servers
* Time: O((n + m) log n)
* Space: O(n + m)
*/
class Solution {
// Keys pack (major, index) into one long: indices are below 2^18.
private static final int SHIFT = 18;
private static final long MASK = (1L << SHIFT) - 1;
public int[] assignTasks(int[] servers, int[] tasks) {
int n = servers.length, m = tasks.length;
PriorityQueue<Long> free = new PriorityQueue<>(n); // (weight, index)
for (int i = 0; i < n; i++) {
free.add(((long) servers[i] << SHIFT) | i);
}
PriorityQueue<Long> busy = new PriorityQueue<>(n); // (free time, index)
int[] ans = new int[m];
long t = 0;
for (int j = 0; j < m; j++) {
// Task j starts no earlier than it arrives or than task j - 1 started.
t = Math.max(t, j);
if (free.isEmpty()) {
t = Math.max(t, busy.peek() >> SHIFT);
}
while (!busy.isEmpty() && (busy.peek() >> SHIFT) <= t) {
int i = (int) (busy.poll() & MASK);
free.add(((long) servers[i] << SHIFT) | i);
}
int i = (int) (free.poll() & MASK);
ans[j] = i;
busy.add(((t + tasks[j]) << SHIFT) | i);
}
return ans;
}
}