Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Intuition 
3.1.
Code
3.2.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is the time complexity for the insertion of an element in a priority queue?
4.2.
What data structure is used to implement a priority queue?
5.
Conclusion
Last Updated: Mar 27, 2024

Process Tasks Using Servers

Author Saksham Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Tasks scheduling algorithms are defined as a set of rules to get the highest level possible in terms of performance and resource utilization.

How about implementing this as a problem?

Sounds interesting, right? Today, we will see a problem in which we have to assign servers to certain tasks and find out which server has to be assigned to which task according to the constraints given to us.

Also Read, Prefix Sum Array

Understanding the Problem

We have been given two arrays, namely 'SERVERS' and 'TASKS' of lengths ‘N’​​​​​​ and ‘M’, respectively, where SERVERS[i] represent the weight of ‘i’​​​​​​th​​​​ server, and TASKS[j] represent the time needed in seconds to process the ‘j’th​​​​ task.

Initially, all servers are free, and the task queue is empty. This task queue is used to assign tasks to servers. 

  • At any second ‘j’, the ‘j’th task is inserted into the task queue (starting with the 0th task being inserted at second 0). If there are free servers present in the queue, the task will be assigned to the server with the smallest weight, and if there is a tie, it will be assigned to a free server with the smallest index.
  • There can also be a case when there are no free servers and the task queue is not empty. In that case, we will wait until a server becomes free and immediately assign the next task to the server at the top of the task queue. If more than one server becomes free at the same time, then multiple tasks from the task queue will be assigned in the order in which the tasks were inserted.
  • If the server is assigned to a task ‘j’ at the time ‘t’, then it will be free again at t + TASKS[j] seconds.

We have to return an array that will store the index of servers assigned to the particular server at that index.

Let us understand this better by an example.

Input

‘SERVERS’ = [3 ,1 ,2]

‘TASKS’ = [1, 2, 3, 4]

Output

[1, 1, 2 ,1]

Explanation

 The following is a list of events in chronological order:

  • Task 0 is added at second 0 and processed by server 1 until second 1.
  • Task 1 is added at second 1 and processed by server 1 until second 3.
  • Now when task 2 will enter the queue we can see that server 1 is already busy as it’s assigned to task 1 (will become free after 3 seconds). Thus we will look for the next smallest server present in the queue which is server 2.
  • Task 3 is added to the queue, We can see that now server 1 is free whereas server 2 is still busy, so out of server 1 and server 0, server 1 is of small weight so it will be assigned to task 3.

Intuition 

We have to access the server with minimum weight every second. The data structure that can help here is a Min Heap We will need two min heaps, one to store the busy servers and one to store the available servers. Busy queue stores the completion time and index(pair) while available queue stores weight and index.

Now let’s look at the approach.

  1. In the beginning, no server will be in use, so we will put all the servers in our 'AVAILABLE' queue(Min Priority Queue) with their weight and index(using 'i' for iterating over the 'SERVER' array) i.e., {SERVER[i], i}.
  2. Now let us say the new task arrives at the time 'T', then before assigning a server to this task. We have to first free all the servers that have finished their tasks before time 'T' from the busy queue. We can do this by maintaining a 'TIMER' variable inside the while loop to keep a count on time elapsed.
  3. Once we have all the free servers at that point in time, we simply choose the top-most server from the 'AVAILABLE' queue, assign it to our task, and put it in the 'BUSY' queue with its completion time and index, i.e., {TIMER + TASKS[i], i}
  4. After all the above is done, we increment 'TIMER'. We will see in a minute how we will increment it.

But before that, what if, for a certain task ‘i’, there are no available servers?

  1. In this case, we will wait for the topmost server in the ‘BUSY’ queue. In other words, we will wait till any of the servers is free and then choose the one with the smallest weight.
  2. There could also be a case when there is more than one server in the 'BUSY' queue with the same completion time. Let us say 'T.’.Then, we will update our 'TIMER' variable to 'T' and then run our while loop to free up the servers.
  3. Now while task 'i' was waiting for a free server, it is possible that other tasks also came up. These tasks will get scheduled at the same time as task 'i' (multiprocessing feature). Thus we will update time as TIMER' = max(TIMER, i + 1) implements.

Below is the code for the above approach.

Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> assignTasks(vector<int> &servers, vector<int> &tasks)
{
    // Declaring min priority queues.
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> busy, available;

    vector<int> ansArray;
    int timer = 0;
    int i = 0;

    // Initially, all servers are free, so pushing them into the 'AVAILABLE' queue.
    while (i < servers.size())
    {
        available.push({servers[i], i});
        i++;
    }

    i = 0;
   
    while (i < tasks.size())
    {
        // If no server is free.
        if (available.empty())
        {
            int top = busy.top().first;
            timer = top;
        }

        // Finding the server with minimum weight.
        while (busy.empty() == false && busy.top().first <= timer)
        {
            int index = busy.top().second;
            available.push({servers[index], index});
            busy.pop();
        }

        int serverIndex = available.top().second;
        available.pop();

        // Storing the answer.
        ansArray.push_back(serverIndex);
        busy.push({timer + tasks[i], serverIndex});

        // Updating 'TIMER'.
        timer = max(timer, i + 1);
        i++;
    }
    return ansArray;
}

int main()
{

    int serverSize;
    int tasksSize;
    cin >> serverSize >> tasksSize;
    vector<int> servers(serverSize, 0);
    vector<int> tasks(tasksSize, 0);

    // Taking input.
    for (int i = 0; i < serverSize; i++)
        cin >> servers[i];
    for (int i = 0; i < tasksSize; i++)
        cin >> tasks[i];

    // Answer array.
    vector<int> ansArray = assignTasks(servers, tasks);
    for (int i = 0; i < ansArray.size(); i++)
        cout << ansArray[i] << " ";
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Input

3 6
3 3 2
1 2 3 2 1 2

Output

2 2 0 2 1 2

Complexity Analysis

Time Complexity

O((N + M) * logN), where ‘N’ is the size of task array and ‘M’ is the size of the ‘SERVERS’ array.

In any case, the queue will at max contain N elements thus insertion in the queue will cost us logN time. Here we will insert a total of N+M tasks in the worst-case Thus the time taken will be O((N + M)* logN).

Space Complexity

O(M), where ‘M’ is the size of the ‘SERVERS’ array.

We are using two priority queues that can have at max ‘M’ elements, thus extra space required is of order ‘M’.

Frequently Asked Questions

What is the time complexity for the insertion of an element in a priority queue?

The time complexity of insertion of an element in a priority queue is O(logN) where N is the size of the Queue

What data structure is used to implement a priority queue?

A priority queue is implemented using a heap data structure. It can be either a max heap or a min heap depending upon the requirements.

Conclusion

Now, you have understood how to solve the problem of Process Tasks Using Servers.

We solved the question with the help of the min priority queue, which is implemented using the heap. We also saw various edge cases where there can be no server available at the moment to more than one server available. But this is not all, and you should not stop here, so head over to our practice platform Coding Ninjas Studio to practice top problems and many more. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Recommended Problem - K Closest Points To Origin

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Till then, Happy Coding!

Live masterclass