1882. Process Tasks Using Servers - cocoder39/coco39_LC GitHub Wiki

1882. Process Tasks Using Servers

Task with lower index is executed first, so task[i] will either be executed at time i if there is free server at time i or task[i] will block the execution of remaining tasks until there is at least one free server

time complexity: M servers and N tasks then T = O(M+ N * log M)

For-loop will be executed N times. Suppose each loop we pop a_i servers out from busy. Also it is guaranteed that we add 1 server back to busy in each loop. At the end of the for-loop, len(busy) = n - (a1+a2+ .. an) = 0 so a1 + a2 + an = n

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:        
        free = []
        for i, weight in enumerate(servers):
            free.append((weight, i))
        heapq.heapify(free)
        
        busy = [] 
        res = []
        for i, task in enumerate(tasks):
            while busy and i >= busy[0][0]:
                _, weight, idx = heapq.heappop(busy)
                heapq.heappush(free, (weight, idx))
                    
            if free:
                w, j = heapq.heappop(free)
                heapq.heappush(busy, (i+tasks[i], w, j))  
            else:
                time, w, j = heapq.heappop(busy)
                heapq.heappush(busy, (time+tasks[i], w, j))  
    
            res.append(j)
                      
        return res