Process Tasks Using Servers

How it works

This is a variation of the two-heap approach with slightly different state tracking. Instead of storing finish time separately, we embed the last known free time within the available heap entries. When transferring servers between heaps, we update this time accordingly. The logic remains the same: efficiently pick the best available server using heaps.

Steps

1. Create two heaps:
   • available: min-heap storing (weight, index, timeFree) for available servers.
   • unavailable: min-heap storing (timeFree, weight, index) for busy servers.
2. Add all servers to available with initial timeFree of 0.
3. For each task at index i:
   • Move servers from unavailable to available while their finish time is at or before i, or while available is empty (must wait for a server).
   • Pop the best server from available.
   • Assign the task and push the server to unavailable with updated finish time: max(timeFree, i) + task duration.
4. Return the result array.

Complexity

• Time complexity: O((n + m) log n)
• Space complexity:
  • O(n) extra space.
  • O(m) space for the output array.

Where m is the number of tasks and n is the number of servers.

Things to watch for

Incorrect Heap Ordering for Server Selection

When no servers are available at time t, you must wait until the earliest server becomes free. A common mistake is not correctly ordering the unavailable heap by finish time, or forgetting to move all servers that become free at that time back to the available heap. Multiple servers might become available simultaneously.

Not Advancing Time When All Servers Are Busy

If all servers are busy when a task arrives, you must jump time forward to when the next server becomes free. Forgetting this causes an infinite loop or incorrect assignments. The time should be set to unavailable.peek().finishTime, not incremented by 1.

Wrong Tie-Breaking Logic in Priority Queue

The problem requires selecting the server with the smallest weight, and among ties, the smallest index. Implementing the comparator incorrectly (e.g., comparing indices before weights) leads to wrong server assignments. Ensure the primary comparison is on weight and secondary on index.

from typing import List
import heapq

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        res = []
        available = [[weight, i, 0] for i, weight in enumerate(servers)]
        unavailable = []
        heapq.heapify(available)

        for i, task in enumerate(tasks):
            while unavailable and unavailable[0][0] <= i or not available:
                timeFree, weight, index = heapq.heappop(unavailable)
                heapq.heappush(available, [weight, index, timeFree])

            weight, index, timeFree = heapq.heappop(available)
            res.append(index)
            heapq.heappush(unavailable, [max(timeFree, i) + task, weight, index])

        return res

class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        int n = servers.size(), m = tasks.size();
        vector<int> res(m);

        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> available;
        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> unavailable;

        for (int i = 0; i < n; ++i) {
            available.push({servers[i], i, 0});
        }

        for (int i = 0; i < m; ++i) {
            while (!unavailable.empty() && (unavailable.top()[0] <= i ||
                   available.empty())) {
                auto [timeFree, weight, index] = unavailable.top();
                unavailable.pop();
                available.push({weight, index, timeFree});
            }

            auto [weight, index, timeFree] = available.top();
            available.pop();
            res[i] = index;
            unavailable.push({max(timeFree, i) + tasks[i], weight, index});
        }

        return res;
    }
};