iT邦幫忙

1

【小馬的LeetCode練功坊】621. Task Scheduler (Medium) ,排程問題,每項工作有冷卻時間,要多長時間做完?

參考題目: 621. Task Scheduler
題意: 給你一堆工作和數字n,每項工作要做1分鐘,n代表相同的工作必順間隔n分鐘再做,問你將所有工作作完要花多少時間?

範例:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
說明: 工作安排為: A->B->閒置->A->B->閒置->A->B,共8分鐘。

思路解析

這一題不是很好想,先想只有一種工作的情形,
假設現在要做5次工作A,必須間隔n分鐘才能再做相同的工作,
那麼工作安排一定是:
A(做1分鐘)->閒置(n分鐘)->A(做1分鐘)->閒置(n分鐘)->A(做1分鐘)->閒置(n分鐘)->A(做1分鐘)->閒置(n分鐘)->A(做1分鐘),
工作時間為(n+1)*(5-1) + 1

主要想法就是是,我們希望閒置時間愈少愈好
這樣浪費沒工作的時間就愈少

因此我們以出現次數最多的工作為主,
在間隔中盡量安排工作給其它次數少的,
例如要做5個A、4個B、4個C的工作,n=1
只有5個A工作的工作狀況為:
「A_A_A_A_A」(_是閒置的時間)

加入B,C之後,便可以把B, C都插入間隔,
變成「ABCABCABCABCA」,這樣就沒有閒置時間的浪費了

但是若出現次數最多的工作,譬如3個A、3個B好了,
你就沒辦法把一個工作插入另一個工作的間隔,
而需要把AB看做一個整體,再插入次數少的工作
「AB_AB_AB」

python程式解

most_freq是出現最多的工作次數,
found_most是出現最多的次數有幾份

以工作「5個A、5個B、4個C、1個D」為例,
出現最多的工作次數為5次,所以most_freq = 5

有兩份工作都出現最高次數5,,所以found_most = 2

(most_freq - 1) * (n + 1) + found_most)指的是若將出現最多的工作次數當做整體,
至少會花的時間
另外,假設工作能安排到完全沒有閒置時間,至少會做「工作數量總和」的時間

因此,取max(len(tasks), (most_freq - 1) * (n + 1) + found_most)即為所求,
當次數少的工作沒有完全填滿閒置時間,時間就是(most_freq - 1) * (n + 1) + found_most);
若次數少的工作完全填滿閒置時間,時間就是max(len(tasks)

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = Counter(tasks)
        most_freq = freq.most_common()[0][1]
        found_most = sum(val == most_freq for val in freq.values())
        return max(len(tasks), (most_freq - 1) * (n + 1) + found_most)

尚未有邦友留言

立即登入留言