使用服务器处理任务

Question

leetcode中的一个问题：https://leetcode.com/problems/process-tasks-using-servers。我有一个简单的解决方案，就是使用min堆存储所有服务器，使用字典检查一次是否有空闲的服务器。但它不可能通过所有的测试案例(26/36)。有人能帮我指出我的缺点吗？

问题：

​

您将获得两个0索引整数数组服务器和长度为n的任务。

和我

分别使用。服务器我是i的权重。

这是

服务器，任务J是处理j#所需的时间。

这是

任务以秒为单位。

使用任务队列将任务分配给服务器。最初，所有服务器都是免费的，队列是空的。

在第二个j，jth任务被插入到队列中(从插入第二个0的第0任务开始)。只要有空闲服务器，队列不是空的，队列前面的任务就会被分配给权重最小的空闲服务器，如果是领带，则分配给索引最小的空闲服务器。

如果没有空闲服务器，队列也不是空的，我们将等到服务器空闲后立即分配下一个任务。如果多个服务器同时空闲，那么队列中的多个任务将按照上述权重和索引优先级顺序分配。

在第二个t处分配任务j的服务器将在第二个t+任务J上再次空闲。

构建一个数组ans

长度m，其中ansJ是服务器j的索引。

这项任务将分配给。

返回数组ans

。

示例1：

输入: servers = 3,3,2，任务= 1,2,3,2,1,2输出：2，2，0，2，1解释:按时间顺序排列的事件如下：

• 在第二个0，任务0被添加和处理使用服务器2直到第二个1。
• 在第二个1，服务器2成为免费的。任务1使用服务器2添加和处理，直到第二个3。
• 在第二个任务2中，任务2被添加并使用服务器0处理，直到第二个5。
• 在第二个3，服务器2成为免费的。任务3是使用服务器2添加和处理的，直到第二个5。
• 在第二个4中，任务4被添加并使用服务器1处理，直到第二个5。
• 在第二阶段，所有服务器都是免费的。任务5是使用服务器2添加和处理的，直到第二个7。

​

from heapq import *

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        
        h = []
        N = len(servers)
        M = len(tasks)
        freeDic = {}
        res = []
        for i in range(N):
            heappush(h, (servers[i], i))
        time = 0
        j = 0
        while j < M:
            if time in freeDic:
                for freeServer in freeDic[time]:
                    heappush(h, freeServer)
                del freeDic[time]
            if len(h) > 0:
                s = heappop(h)
                res.append(s[1])
                timeToFree = time + tasks[j]
                if timeToFree in freeDic:
                    freeDic[timeToFree].append(s)
                else:
                    freeDic[timeToFree] = [s]
                j += 1
            time += 1
            
                
        return res

失败案例：

Input:
[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]
[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]

Output:
[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]

Expected:
[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]

Answer 1

我尝试过这个问题，但没有发任何东西，因为我认为它是不主题的；然而，我想这是错误的。由于您正在LeetCode上解决谜题，所以我假设您想要获得编写自己的实现的满足感，所以我将不发布我自己的解决这个问题的方法。我相信您当前的代码有两个问题，都与时间管理有关。

问题1:在任何特定的秒内，您都不会开始一个以上的任务。这是正确的方法，如果总是有一个免费的服务器。但是，如果当任务应该启动时，服务器都很忙，那么在下一秒，我们就有了两个可以启动的任务。如果有两个免费服务器，我们应该立即开始这两个任务。一个简短的例子：

# Two servers, with equal weights:
servers = [1, 1]

# Four tasks:
task durations       = [3, 2, 1, 1]
desired start times  =  0  1  2  3
implied finish times =  3  3  3  4

# What happens:
- At time=3, both previously-busy servers will be free.
- We should start the last two tasks immediately.
- But your code waits until time=4 to start the last one.

# Expected result vs actual:
expected = [0, 1, 0, 1]
actual   = [0, 1, 0, 0]

问题2:时间..。增加..。太..。慢慢地。当前代码每循环迭代增加1秒的时间。在第一个N秒( N是任务数)期间，这是有意义的。但更深层次的未来，这种缓慢的步伐可能是一个问题。如果LeetCode要用非常大的任务持续时间来满足您的程序任务，那么这个循环就会在很长一段时间内被不必要地消耗掉。例如，假设与上面的示例相同的服务器具有以下任务：[999999999, 999999999, 1, 1]。人类可以快速计算出正确的答案，但你的代码不能。诚然，LeetCode将任务期限限制为200000 (并不是很大的数字，因此您可以很快地完成它)，但根据我在网站上发布的关于这个问题的答案的经验，每当我天真地增加时间时，我的解决方案就会失败。关键是只检查相关的时间，按正确的顺序，当然.这听起来是另一个堆的一个很好的用例。