We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Process Tasks Using Servers

Number: 2012

Difficulty: Medium

Paid? No

Companies: Amazon, Lyft, PayPal, TikTok, X

Problem Description

Given two arrays – servers and tasks – assign each task to a server according to the following rules: at each second j, the jth task is added to the queue; while the queue is not empty and free servers exist, take the task at the front and assign it to the available server with the smallest weight (breaking ties by smallest index). If no server is free, wait until the next server finishes its current task. A server that starts task j at time t becomes free at time t + tasks[j]. Return an array ans where ans[j] is the index of the server which processes the jth task.

Key Insights

  • Use a min-heap to track free servers sorted by weight and index.
  • Use another min-heap to manage busy servers, prioritized by when they become free.
  • Keep track of the current time, taking into account task arrival times.
  • If no server is free at the time of task arrival, fast-forward time to when the next server becomes available.
  • Always reassign servers from the busy heap to the free heap when they complete their tasks.

Space and Time Complexity

Time Complexity: O(m log n), where m is the number of tasks and n is the number of servers, since each task assignment may require heap operations. Space Complexity: O(n + m) primarily for the heaps and the result array.

Solution

We use two heaps:

  1. Free Servers Heap: stores tuples (server weight, server index), sorted so that the server with the smallest weight (and then smallest index) is always at the top.
  2. Busy Servers Heap: stores tuples (finish time, server weight, server index), ordered by finish time. When a server is busy processing a task, it resides in this heap. The algorithm maintains a current time variable. For each task arriving at time j, time is updated to ensure it is at least j. Servers that become free on or before the current time are moved from the busy heap to the free heap. If no free server is available, the current time jumps to the finish time of the next server to be available. The task is then assigned to the free server at the top of the free heap, and the server's next free time is computed and added to the busy heap. This continues until all tasks are assigned.

Code Solutions

# Python solution using heaps from the heapq module
import heapq

def processTasks(servers, tasks):
    # free_servers heap: (server_weight, server_index)
    free_servers = [(weight, idx) for idx, weight in enumerate(servers)]
    heapq.heapify(free_servers)
    
    # busy_servers heap: (finish_time, server_weight, server_index)
    busy_servers = []
    
    n = len(tasks)
    result = [0] * n  # To store the server assigned to each task
    time = 0        # Current time
    
    # Iterate through each task (arrival time is j)
    for j, task_time in enumerate(tasks):
        time = max(time, j)  # Ensure current time is at least j

        # Move servers that have completed tasks from busy_servers to free_servers
        while busy_servers and busy_servers[0][0] <= time:
            finish_time, weight, server_idx = heapq.heappop(busy_servers)
            heapq.heappush(free_servers, (weight, server_idx))
        
        # If no free servers, fast-forward time to when the next server becomes free
        if not free_servers:
            time = busy_servers[0][0]
            while busy_servers and busy_servers[0][0] <= time:
                finish_time, weight, server_idx = heapq.heappop(busy_servers)
                heapq.heappush(free_servers, (weight, server_idx))
        
        # Assign the task to the free server with smallest weight (and index)
        weight, server_idx = heapq.heappop(free_servers)
        result[j] = server_idx
        
        # Add the server into busy_servers with its new finish time
        heapq.heappush(busy_servers, (time + task_time, weight, server_idx))
    
    return result

# Example usage:
# servers = [3,3,2]
# tasks = [1,2,3,2,1,2]
# print(processTasks(servers, tasks))  # Output: [2,2,0,2,1,2]
← Back to All Questions