python - Codewars 中的超市排队编程问题

Question

问题如下:超市的自助收银台前排起了长队。您的任务是编写一个函数来计算所有客户结帐所需的总时间!

输入:客户:代表队列的正整数数组。每个整数代表一个客户，其值是他们结账所需的时间。n:正整数，收银台数量。

输出:该函数应返回一个整数，即所需的总时间我的代码是

import math
def empty(seq):
    is_empty=True
    for i in seq:
        if i>0:
            is_empty=False
            break
    return is_empty
def checks(cust,n):
    if len(cust)==0:
        return 0
    if n==1:
        sum=0
        for i in cust:
            sum+=i
        return sum
    elif len(cust)<=n:
        return max(cust)
def queue_time(customers, n):
    if len(customers)==0 or n==1 or len(customers)<=n:
            return checks(customers,n)
    main_sum=0
    tills=[0]*n
    leng=len(customers)
    if leng>n:
        for i in range(n):
            tills[i]=customers[i]
    t_len=len(tills)
    main_loop=t_len
    while(main_loop<leng and not empty(tills)):
        least=min(tills)
        if least==0:
            least = min(i for i in tills if i > 0)
        for inner in range(t_len):
            if tills[inner]>0:
                tills[inner]-=least
        main_sum+=least
        if main_loop<leng:
            for fill_zero in range(t_len):
                if tills[fill_zero]==0:
                    tills[fill_zero]=customers[main_loop]
                    main_loop+=1
    return main_sum
print(queue_time([2,2,3,3,4,4], 2)) #should equal 9 but the result is 5 !

输出应该等于 9，但我的是 5

Answer 1

实际上，您可以通过 0 次导入和 5 行代码来完成此操作。
您创建可用收银台列表，迭代客户结帐时间，添加到第一个索引并在列表上运行排序，以便最大的 int (结帐时间最长)是最后一个索引。
然后，每次迭代都会将下一个结帐时间添加到第一个索引，因为它是下一个可用的直到等等。
然后只需返回列表中最大的数字即可。

def queue_time(customers: list[int], n: int) -> int:
    tills = [0]*n
    for i in customers:
      tills[0] += i
      tills.sort()
    return max(tills)

上面的方法对于少量队列和客户来说很好，但对于较大的池来说效率稍低，这就是 heapq 的用武之地。它避免了对每个客户的整个收银台列表进行排序。相反，它使用堆以最短的队列有效地查找和更新钱柜。

import heapq

def queue_time(customers: list[int], n: int) -> int:
    tills = [0]*n
    heapq.heapify(tills)
    for i in customers:
        smallest_till = heapq.heappop(tills)
        heapq.heappush(tills, smallest_till + i)
    return max(tills)

• 更新了 typehints 和 heapq 示例