codewars(python)練習(xí)筆記十：計(jì)算超市排隊(duì)時(shí)長

題目

There is a queue for the self-checkout tills at the supermarket. Your task is write a function to calculate the total time required for all the customers to check out!

The function has two input variables:

customers: an array (list in python) of positive integers representing the queue. Each integer represents a customer, and its value is the amount of time they require to check out.

n: a positive integer, the number of checkout tills.

The function should return an integer, the total time required.

EDIT: A lot of people have been confused in the comments. To try to prevent any more confusion:

There is only ONE queue, and

The order of the queue NEVER changes, and

Assume that the front person in the queue (i.e. the first element in the array/list) proceeds to a till as soon as it becomes free.

The diagram on the wiki page I linked to at the bottom of the description may be useful.

So, for example:

queue_time([5,3,4], 1)

# should return 12

# because when n=1, the total time is just the sum of the times

queue_time([10,2,3,3], 2)

# should return 10

# because here n=2 and the 2nd, 3rd, and 4th people in the

# queue finish before the 1st person has finished.

queue_time([2,3,10], 2)

# should return 12

N.B. You should assume that all the test input will be valid, as specified above.

P.S. The situation in this kata can be likened to the more-computer-science-related idea of a thread pool, with relation to running multiple processes at the same time: https://en.wikipedia.org/wiki/Thread_pool

Test case:

queue_time([2,3,10], 2) should be 12

queue_time([], 5) should be 0

queue_time([2], 5) should be 2

queue_time([1,2,3,4,5], 100) should be 5

queue_time([2,3,10,2,3], 2) should be 12

題目大意:

這道題是經(jīng)典的超市購物排隊(duì)問題：有一個(gè)隊(duì)列 customers[]，隊(duì)列中每個(gè)元素是當(dāng)前顧客的處理時(shí)長，有 n 個(gè)購物臺(tái),可以同時(shí)處理n個(gè)客戶。這是題目大意，求的是隊(duì)列的處理時(shí)長。

特別注意：

只有一個(gè)隊(duì)列，

隊(duì)列處理順序不能變，

假設(shè)隊(duì)列中的前面的人(即數(shù)組/列表中的第一個(gè)元素)在有購物臺(tái)空閑的時(shí)候就會(huì)繼續(xù)前進(jìn)。

我的解法：

#!/usr/bin/python

def queue_time(customers, n):

if customers == []:

return 0

if len(customers) < n:

return max(customers)

list_temp = [customers[i] for i in range(0,n)]

for item in range(n,len(customers)):

list_temp[list_temp.index(min(list_temp))] += item

return max(list_temp)

牛逼解法：

#!/usr/bin/python

def queue_time(customers, n):

list_temp = [0]*n

for item in customers:

list_temp[list_temp.index(min(list_temp))] += item

return max(list_temp)

我跟最牛逼的解法之間的差距在于：我意識(shí)到了 list_temp 通過 [customers[i] for i in range(0,n)]這樣創(chuàng)建，絕對(duì)不是最佳解法。但沒有想到，可以直接生成長度為n 的空數(shù)組。

另一個(gè)牛逼解法：

def queue_time(customers, n):

queues = [0] * n

for i in customers:

queues.sort()

queues[0] += i

return max(queues)

相對(duì)于上一個(gè)，sort() 要比min() 算法復(fù)雜度高一些。

另一個(gè)牛逼解法：

def queue_time(cs, n):

def serve(q,c): return sorted([q[0]+c] + q[1:])

return max(reduce(serve, cs, [0]*n))

利用reduce(),相當(dāng)精奇的思路。

總結(jié)

以上是生活随笔為你收集整理的python中计算排队等待时间_codewars（python）练习笔记十：计算超市排队时长的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。