Process Tasks Using Servers - Leetcode 1882 - Python

0:00 - Read the problem
4:30 - Drawing Explanation
11:11 - Coding Explanation

leetcode 1882 - leetcode contest problem

#servers #tasks #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[chandravo]

We can optimize the space complexity further by only storing the time available and the index, and not the weight of the server. We can get knowledge about the weight of the server from the server array.

[xueli]

Hey man, you never let me down! thank you!

[orellavie]

I think there is some little bug with this solution!
The heapify won't take the index of two same weight servers as a matter. For example, two servers idx 0 and idx 1 with 5 weight. After heapify they are in order. Let's say idx 0 is used, and then idx1 is used for shorter task. Therefore, idx will be back sooner, and idx 0 will return after that. If they're both on the heap now, who promised that idx 0 will be chosen and not idx1. Idx1 will be chosen is a more probable event.

[sadmanabedin]

I thought the exact same thing but got wrong answer.
After examining I realized what was my mistake:
When there were no free servers, I updated time to the moment when a the topmost server from occupied heap will be free.
But when there were free servers, I used to increment time by 1 which is a mistake, because in case time is already bigger then the current index of the task, there is no point increasing it. Because time getting increased by 1 means it might release some more server on the next iteration which was not supposed to be freed at that very moment when the next task was pushed to the queue.

by the way, you don't need to store all those three parameters in the unavailable heap, just store the index of the task, that'll suffice.

[arpanbanejee]

Thanks for the awesome explanation! I have one doubt here, why are we using a while loop for popping from the unavailable queue, we can only use a if and just take out that single server which is free and put it in the available queue, why are we bothered with all the servers that have become free in the unavailable queue, when they are already arranged based on time, weight and index

[jimmyliaouwu]

Wow, so this is Google interview question?

[chirag]

Can we not use the dictionary to check at time T what are the servers will be available
: for example I am currently at time 0 and task take 2 seconds so I can push it in the dictionary that at t = 3 it will be available

below is the code


```
class Solution:
def assignTasks(self, servers, tasks):
mins = []
ans = []
td = defaultdict(lambda: [])
for i, v in enumerate(servers):
heapq.heappush(mins, (v, i))
val = 0
time = 0
while val < len(tasks):
if len(mins):
cur = heapq.heappop(mins)
td[time + tasks[val]].append(cur)
ans.append(cur[1])
val += 1
time += 1
for ntval in td[time]:
heapq.heappush(mins, ntval)
return ans

[rogercheng]

why do we need to advance the time if there none available?

[devanshipatel]

Just one thing is missing in your live code, heapq.heapify(unavail) after initialization of unavail heap as list! Thank you for simple explanation.

[rhapsodyLi]

We tend to use the unavailable server, so why we didn't pop newly available servers before checking if no servers available?
I mean:

while unavail and t >= unavail[0][0]: # pop newly available servers
timefree, weight, index = heapq.heappop(unavail)
heapq.heappush(available, (weight, index))

if len(available) == 0: # check if no servers available
t = unavail[0][0]

[jayeshnagarkar]

// PLEASE SOMEONE HELP ME, , IT IS NOT PASSING ONE TEST CASE. I AM STUCK FOR MANY DAYS. I HAVE ABOVE AVERGAGE LEETOCODE //SKILLS

class Solution {
public int[] assignTasks(int[] servers, int[] tasks) {
Queue<int[]> available = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) :
Integer.compare(a[1], b[1])); //weight, index
Queue<int[]> unavailable = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2])); //weight, index, freeTime
if(servers.length >= + "---" + servers[36]);

IntStream.range(0, servers.length).mapToObj(i -> new int[] {servers[i], i}).forEach(available :: add);

int[] result = new int[tasks.length];

int time = 0;
int idx = 0;

while(idx < tasks.length) {
while(!unavailable.isEmpty() && unavailable.peek()[2] <= time) {
int[] cur = unavailable.poll();
available.add(new int[] {cur[0], cur[1]});
}

if(available.isEmpty()) {
time = unavailable.peek()[2];
}
else{
int[] cur = available.poll();
unavailable.add(new int[] {cur[0], cur[1], time+tasks[idx]});
result[idx++] = cur[1];
time++;

}
}
return result;


}
}

[indsonusharma]

Nice explanation bro!! Though its TLE on leetcode right now.🥲