无法找到有问题的边缘案例 "Process Tasks Using Servers" 在 leetcode 每周竞赛 243 中提出

Question

[link转题](https://leetcode.com/problems/process-tasks-using-servers/)。问题陈述在提供的 link 中写得很清楚。我已经强调了我的结果与预期结果之间的差异。

我无法弄清楚我错过了哪种极端情况或条件？

如果问题陈述仍然不清楚，请告诉我。

更新:更新的方案在评论区

import heapq
class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        serverPriority = [(name, index) for index, name in enumerate(servers)]
        
        # this sorts the server based on the priority order specified in the problem statement.
        serverPriority.sort()
         
        """
         A new ID is given to the server after sorting, 
         which is basically the index number of the servers 
         in **serverPriority** list.
       """
        serverId = [i for i in range(len(servers))]
        heapq.heapify(serverId)
        
        res = [-1] * len(tasks)
        

        runningServers = []
        heapq.heapify(runningServers)
        
        currTime = 0
        for j in range(len(tasks)):
            # if no servers are running then selects a server from the pool of available servers.
            if len(runningServers) == 0:
                ID = heapq.heappop(serverId)
                res[j] = serverPriority[ID][1]
                
                heapq.heappush(runningServers, (currTime + tasks[j], ID))
            else:
                """
                 if some servers are running then it checks whether any server
                 is going to stop execution at **currentTime**, or before that 
                 and then selects that server for running another task.
                """
                if currTime >= runningServers[0][0]:
                    time, ID = heapq.heappop(runningServers)
                    res[j] = serverPriority[ID][1]
                    
                    heapq.heappush(runningServers, (currTime + tasks[j], ID))
                else:
                    """
                     case when none of the running server can be chosen. 
                     so it chooses one from the pool.
                    """
                    if len(serverId) > 0:
                        ID = heapq.heappop(serverId)
                        res[j] = serverPriority[ID][1]
                        
                        heapq.heappush(runningServers, (currTime + tasks[j], ID))
                    else:
                        """
                        If no servers are available in pool then it has to wait 
                         for one of the running server to stop.
                        """
                        time, ID = heapq.heappop(runningServers)
                        currTime = time
                        res[j] = serverPriority[ID][1]
                        
                        heapq.heappush(runningServers, (currTime + tasks[j], ID))
            currTime += 1
            
        return res

通过的测试用例：

服务器 = [3,3,2]，任务 = [1,2,3,2,1,2]

预期：[2,2,0,2,1,2]

服务器 = [5,1,4,3,2]，任务 = [2,1,2,4,5,2,1]

预期：[1,4,1,4,1,3,2]

失败的测试用例：

servers = [338,890,301,532,284,930,426,616,919,267,571,140,716,859,980,469,628,490,195,664,925,652,503,301,917,563,82,947,910,451,366,190,253,516,503,721,889,964,506,914,986,718,520,328,341,765,922,139,911,578,86,435,824,321,942,215,147,985,619,865]

tasks =[773,537,46,317,233,34,712,625,336,221,145,227,194,693,981,861,317,308,400,2,391,12,626,265,710,792,620,416,267,611,875,361,494,128,133,157,638,632,2,158,428,284,847,431,94,782,888,44,117,489,222,932,494,948,405,44,185,587,738,164,356,783,276,547,605,609,930,847,39,579,768,59,976,790,612,196,865,149,975,28,653,417,539,131,220,325,252,160,761,226,629,317,185,42,713,142,130,695,944,40,700,122,992,33,30,136,773,124,203,384,910,214,536,767,859,478,96,172,398,146,713,80,235,176,876,983,363,646,166,928,232,699,504,612,918,406,42,931,647,795,139,933,746,51,63,359,303,752,799,836, 50,854,161,87,346,507,468,651,32,717,279,139,851,178,934,233,876,797,701,505,878,731,468,884,87,921,782,788,803,994,67,905,309,2,85,200,368,672,995,128,734,157,157,814,327,31,556,394,47,53,755,721,159,843]

预期：[26,50,47,11,56,31,18,55,32,9,4,2,23,53,43,0,44,30,6,51,29, 51,15,17,22,34,38,33,42,3,25,10,49,51,7,58,16,21,19,31,19,12,41,35,45,52, 13,59,47,36,1,28,48,39,24,8,46,20,5,54,27,37,14,57,40,59,8,45,4,51,47, 7,58,4,31,23,54,7,9,56,2,46,56,1,17,42,11,30,12,44,14,32,7,10,23,1, 29,27,6,10,33,24,19,10,35,30,35,10,17,49,50,36,29,1,48,44,7,11,24,57,42, 30,10,55,3,20,38,15,7,46,32,21,40,16,59,30,53,17,18,22,51,11,53,36,57,26, 5,36,56,55,31,34,57,7,52,37,31,10,0,51,41,2,32,25,0,7, 49,47,13,14,24,57,28,4,45,43,39,38,8,2,44,45,29,25,25,12,54,5,44,30,27, 23,26,7,33,58,41,25,52,40,58,9,52,40]

我的结果：[26,50,47,11,56,31,18,55,32,9,4,2,23,53,43,0,44,30,6,51,29 ,51,15,17,22,34,38,33,42,3,25,10,49,51,7,58,16,21,19,31,19,12,41,35,45,52 ,13,59,47,36,1,28,48,39,24,8,46,20,5,54,27,37,14,57,40,59,8,45,4,51,47 ,7,58,4,31,23,54,7,9,56,2,46,56,1,17,42,11,30,12,44,14,32,7,10,23,1 ,29,27,6,10,33,24,19,10,35,30,35,10,17,49,50,36,29,1,48,44,7,11,24,57,42 ,30,10,55,3,20,38,15,7,46,32,21,40,16,59,30,53,17,18,22,51,11,53,36,57,26 ,5,56,36,55,31,34,57,7,52,37,31,10,0,51,41,2,32,25,0,7 ,49,47,13,14,24,57,28,4,45,43,39,38,8,2,44,45,29,25,25,12,54,5,44,30,27 ,23,26,7,33,58,41,25,52,40,58,9,52,40]

Answer 1

要记住的一点：runningServers 堆内存在的服务器比池[=23] 内存在的服务器具有更高的优先级=]serverId 正在等待一些任务。

现在，假设我们有 3 个服务器 s1、s2、s3，优先级顺序为 s1 > s2 > s3，以及 4 个任务 t1、t2、t3 , t4 随着到达时间递增。另外，假设当我们要为 t4 分配服务器时，到那时 s2 和 s3 就空闲了。

现在，理想情况下，我们应该为任务 t4 选择服务器 s2，但上面给出的算法将为 t4 选择 s3，因为它在服务器的完成时间维护一个最小堆属性。因此，重要的是首先释放所有 finish time <= currTime 的服务器，然后从池中为 t4 选择一个新服务器。

现在，如果无法从 runningServer 中选择服务器并且我们在池 serverId 中甚至没有任何可用服务器会发生什么情况？

解决方案: 我们需要等待一段时间才能让其中一台服务器免费。假设一个服务器将在 time = x ms 释放，也有可能有多个服务器将在 time = x 释放女士

所以，问题陈述的最终解法是：

serverPriority = [(name, index) for index, name in enumerate(servers)]
        
        serverPriority.sort()

        serverId = [i for i in range(len(servers))]
        heapq.heapify(serverId)
        
        res = [-1] * len(tasks)
        
        runningServers = []
        heapq.heapify(runningServers)
        
        currTime = 0
        j = 0
        while j < len(tasks):
            currTime = max(currTime, j)
            
            if len(runningServers) == 0:
                ID = heapq.heappop(serverId)
                res[j] = serverPriority[ID][1]
                
                heapq.heappush(runningServers, (currTime + tasks[j], ID))
            else:
                # Here, we are first freeing up the servers
                while len(runningServers) > 0 and currTime >= runningServers[0][0]:
                    time, ID = heapq.heappop(runningServers)
                    heapq.heappush(serverId, ID)
            
                if len(serverId) > 0:
                    ID = heapq.heappop(serverId)
                    res[j] = serverPriority[ID][1]

                    heapq.heappush(runningServers, (currTime + tasks[j], ID))
                else:
                    """
                     here, we are keeping record of the server 
                     with earliest finish time.
                    """
                    time = runningServers[0][0]
                    currTime = time
                    j -= 1
            
            j += 1
            
        return res

无法找到有问题的边缘案例 "Process Tasks Using Servers" 在 leetcode 每周竞赛 243 中提出

Not being able to find an edge case in question "Process Tasks Using Servers" asked in leetcode weekly contest 243

heap

python-3.x