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.
- 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}.
- 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.
- 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}
- 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?
- 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.
- 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.
- 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!