1882. Process Tasks Using Servers LeetCode Solution
In this guide, you will get 1882. Process Tasks Using Servers LeetCode Solution with the best time and space complexity. The solution to Process Tasks Using Servers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Process Tasks Using Servers solution in C++
- Process Tasks Using Servers solution in Java
- Process Tasks Using Servers solution in Python
- Additional Resources
Problem Statement of 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 ith server, and tasks[j] is the time needed to process the jth 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 jth 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
Complexity Analysis
- Time Complexity: O((n + m)\log n)
- Space Complexity: O(n + m)
1882. Process Tasks Using Servers LeetCode Solution in C++
struct T {
int weight;
int index;
int freeTime;
};
class Solution {
public:
vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
const int n = servers.size();
const int m = tasks.size();
vector<int> ans(m);
auto compareFree = [](const T& a, const T& b) {
return a.weight == b.weight ? a.index > b.index : a.weight > b.weight;
};
auto compareUsed = [](const T& a, const T& b) {
if (a.freeTime != b.freeTime)
return a.freeTime > b.freeTime;
if (a.weight != b.weight)
return a.weight > b.weight;
return a.index > b.index;
};
priority_queue<T, vector<T>, decltype(compareFree)> free(compareFree);
priority_queue<T, vector<T>, decltype(compareUsed)> used(compareUsed);
for (int i = 0; i < n; ++i)
free.emplace(servers[i], i, 0);
for (int i = 0; i < m; ++i) { // i := the current time
const int executionTime = tasks[i];
// Pop all the servers that'll be free at time i.
while (!used.empty() && used.top().freeTime <= i) {
const T curr = used.top();
used.pop();
free.push(curr);
}
if (free.empty()) {
T server = used.top();
used.pop();
ans[i] = server.index;
server.freeTime += executionTime;
used.push(server);
} else {
T server = free.top();
free.pop();
ans[i] = server.index;
server.freeTime = i + executionTime;
used.push(server);
}
}
return ans;
}
};
/* code provided by PROGIEZ */1882. Process Tasks Using Servers LeetCode Solution in Java
class T {
public int weight;
public int index;
public int freeTime;
public T(int weight, int index, int freeTime) {
this.weight = weight;
this.index = index;
this.freeTime = freeTime;
}
}
class Solution {
public int[] assignTasks(int[] servers, int[] tasks) {
final int n = servers.length;
final int m = tasks.length;
int[] ans = new int[m];
Queue<T> free =
new PriorityQueue<>((a, b)
-> a.weight == b.weight ? Integer.compare(a.index, b.index)
: Integer.compare(a.weight, b.weight));
Queue<T> used = new PriorityQueue<>(new Comparator<T>() {
@Override
public int compare(T a, T b) {
if (a.freeTime != b.freeTime)
return a.freeTime - b.freeTime;
if (a.weight != b.weight)
return a.weight - b.weight;
return a.index - b.index;
}
});
for (int i = 0; i < n; ++i)
free.offer(new T(servers[i], i, 0));
for (int i = 0; i < m; ++i) { // i := the current time
final int executionTime = tasks[i];
// Poll all servers that'll be free at time i.
while (!used.isEmpty() && used.peek().freeTime <= i)
free.offer(used.poll());
if (free.isEmpty()) {
T server = used.poll();
ans[i] = server.index;
server.freeTime += executionTime;
used.offer(server);
} else {
T server = free.poll();
ans[i] = server.index;
server.freeTime = i + executionTime;
used.offer(server);
}
}
return ans;
}
}
// code provided by PROGIEZ1882. Process Tasks Using Servers LeetCode Solution in Python
class Solution:
def assignTasks(self, servers: list[int], tasks: list[int]) -> list[int]:
ans = []
free = [] # (weight, index, freeTime)
used = [] # (freeTime, weight, index)
for i, weight in enumerate(servers):
heapq.heappush(free, (weight, i, 0))
for i, executionTime in enumerate(tasks): # i := the current time
# Poll all servers that'll be free at time i.
while used and used[0][0] <= i:
curr = heapq.heappop(used)
heapq.heappush(free, (curr[1], curr[2], curr[0]))
if free:
curr = heapq.heappop(free)
ans.append(curr[1])
heapq.heappush(used, (i + executionTime, curr[0], curr[1]))
else:
curr = heapq.heappop(used)
ans.append(curr[2])
heapq.heappush(used, (curr[0] + executionTime, curr[1], curr[2]))
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.