Process Tasks Using Servers - Practice Coding Problems

Process Tasks Using Servers - 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 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 j-th task is inserted into the queue (starting with the 0-th 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.

Input & Output

Example 1 — Basic Server Assignment

$ Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]

› Output: [2,2,0,2,1,2]

💡 Note: Task 0 (time=1) → Server 2 (weight=2, smallest). Task 1 arrives at t=1, Server 2 busy until t=2, so assign to Server 0 (weight=3, index=0). Continue this process for all tasks.

Example 2 — Equal Weight Priority

$ Input: servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]

› Output: [1,4,1,4,1,3,2]

💡 Note: Server 1 has smallest weight (1), so gets first task. When multiple servers are free, choose by smallest weight then smallest index.

Example 3 — Waiting for Servers

$ Input: servers = [10,20], tasks = [5,3,4]

› Output: [0,1,0]

💡 Note: Task 0 → Server 0. Task 1 arrives at t=1, both servers busy, wait until Server 0 finishes at t=5. Task 2 waits for next available server.

Constraints

1 ≤ servers.length, tasks.length ≤ 2 × 10⁵
1 ≤ servers[i], tasks[i] ≤ 2 × 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Servers with weights [3,3,2] and tasks with durations [1,2,3]

Process

Assign each task to available server with smallest weight/index

Output

Array of server indices that handled each task

Key Takeaway

🎯 Key Insight: Use priority queues to efficiently find the optimal server without scanning all servers for each task

Asked in

a Amazon 15 M Microsoft 12 G Google 8 f Meta 6

The key insight is to use priority queues to efficiently manage server assignment. The optimal approach uses two heaps: one for available servers (sorted by weight, then index) and one for busy servers (sorted by completion time). This reduces time complexity from O(m×n) to O(m log n) where m is tasks and n is servers.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(m × n)	O(n)	Simulate the process by checking all servers for each task assignment
Priority Queue Optimization	O(m log n)	O(n)	Use heaps to efficiently track available servers and busy server completion times

Brute Force Simulation — Algorithm Steps

For each task, scan all servers to find free ones
Among free servers, pick one with smallest weight then smallest index
Update server's free time and record assignment

Visualization

Tap to expand

Step-by-Step Walkthrough

Task Arrival

New task arrives, scan all servers

Find Best

Compare weights and indices to find optimal server

Assign

Update server's free time and record assignment

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* solution(int* servers, int serversSize, int* tasks, int tasksSize, int* returnSize) {
    long long* serverFreeTime = (long long*)calloc(serversSize, sizeof(long long));
    int* result = (int*)malloc(tasksSize * sizeof(int));
    *returnSize = tasksSize;
    
    for (int taskIdx = 0; taskIdx < tasksSize; taskIdx++) {
        long long currentTime = taskIdx;
        int taskDuration = tasks[taskIdx];
        
        // Find best available server
        int bestServer = -1;
        for (int i = 0; i < serversSize; i++) {
            if (serverFreeTime[i] <= currentTime) {
                if (bestServer == -1 || servers[i] < servers[bestServer] || 
                    (servers[i] == servers[bestServer] && i < bestServer)) {
                    bestServer = i;
                }
            }
        }
        
        // If no free server, wait for earliest one
        if (bestServer == -1) {
            long long earliestTime = serverFreeTime[0];
            for (int i = 1; i < serversSize; i++) {
                if (serverFreeTime[i] < earliestTime) {
                    earliestTime = serverFreeTime[i];
                }
            }
            currentTime = earliestTime;
            for (int i = 0; i < serversSize; i++) {
                if (serverFreeTime[i] == earliestTime) {
                    if (bestServer == -1 || servers[i] < servers[bestServer] || 
                        (servers[i] == servers[bestServer] && i < bestServer)) {
                        bestServer = i;
                    }
                }
            }
        }
        
        // Assign task to server
        if (currentTime > serverFreeTime[bestServer]) {
            serverFreeTime[bestServer] = currentTime + taskDuration;
        } else {
            serverFreeTime[bestServer] += taskDuration;
        }
        result[taskIdx] = bestServer;
    }
    
    free(serverFreeTime);
    return result;
}

int main() {
    // Simple parsing for arrays [1,2,3]
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int servers[1000], serversSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL && serversSize < 1000) {
        servers[serversSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    int tasks[1000], tasksSize = 0;
    token = strtok(line, "[,]");
    while (token != NULL && tasksSize < 1000) {
        tasks[tasksSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(servers, serversSize, tasks, tasksSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

For each of m tasks, we scan through n servers to find the best available one

✓ Linear Growth

Space Complexity

O(n)

Array to track when each server becomes free

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler