{x}
blog image

Process Tasks Using Servers

You are given two 0-indexed integer arrays servers and tasks of lengths n​​​​​​ and m​​​​​​ respectively. servers[i] is the weight of the i​​​​​​th​​​​ server, and tasks[j] is the time needed to process the j​​​​​​th​​​​ 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 j​​​​​​th task will be assigned to.

Return the array ans​​​​.

 

Example 1:

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:

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.

 

Constraints:

  • servers.length == n
  • tasks.length == m
  • 1 <= n, m <= 2 * 105
  • 1 <= servers[i], tasks[j] <= 2 * 105

Solution Explanation: Process Tasks Using Servers

This problem involves assigning tasks to servers efficiently, considering server weights, task processing times, and server availability. The optimal solution leverages priority queues (min-heaps) to manage both idle and busy servers.

Approach:

  1. Data Structures: We use two min-heaps:

    • idle: Stores idle servers as tuples (weight, server_index). The min-heap orders servers by weight (smaller weight first), then by index (smaller index first in case of weight ties).
    • busy: Stores busy servers as tuples (available_time, weight, server_index). The min-heap prioritizes servers becoming available sooner (smaller available_time), then by weight, and finally by index.

  2. Initialization: Populate idle with all servers and their weights. busy starts empty.

  3. Task Assignment: Iterate through each task:

    • Check for available servers: Remove servers from busy that have become available ( available_time ≤ current time j). Add these freed servers back to idle.
    • Assign the task:
      • If idle is not empty, choose the server with the smallest weight and index from idle, assign it the task, and add it to busy with its new available_time (current time + task processing time).
      • If idle is empty (all servers busy), choose the server from busy that will be free soonest, assign it the task, update its available_time, and put it back into busy.
    • Record the assignment: Add the assigned server's index to the ans array.

  4. Return: After processing all tasks, return the ans array.

Time Complexity: O((n + m) log n), where 'n' is the number of servers and 'm' is the number of tasks. This is dominated by the heap operations (insertion, deletion, and peeking), each taking O(log n) time in a heap of size at most n. We perform these operations at most n + m times (initially adding n servers to idle, then potentially up to m operations per task).

Space Complexity: O(n), as the heaps can hold at most all the servers.

Code (Python):

import heapq
 
class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        idle = [(weight, i) for i, weight in enumerate(servers)]  # (weight, index)
        heapq.heapify(idle)  # Min-heap of idle servers
        busy = []  # (available_time, weight, index)  Min-heap of busy servers
        ans = []
 
        for j, task_time in enumerate(tasks):
            while busy and busy[0][0] <= j:  # Check for available servers
                available_time, weight, index = heapq.heappop(busy)
                heapq.heappush(idle, (weight, index))
 
            if idle:  # Assign task to an idle server
                weight, index = heapq.heappop(idle)
                heapq.heappush(busy, (j + task_time, weight, index))
                ans.append(index)
            else:  # Assign task to the soonest-available busy server
                available_time, weight, index = heapq.heappop(busy)
                heapq.heappush(busy, (available_time + task_time, weight, index))
                ans.append(index)
 
        return ans

The code in other languages (Java, C++, Go, TypeScript) follows the same logic, using their respective priority queue implementations. The key difference lies in the specific syntax and data structure usage for heaps, but the core algorithmic approach remains the same.