30天挑戰！用LeetCode來學程式(28) — Task Scheduler

這次的題目還蠻生活化的，是個工作排程的問題。

題目

You are given a char array representing tasks CPU need to do. It contains capital letters A to Z where each letter represents a different task. Tasks could be done without the original order of the array. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

You need to return the least number of units of times that the CPU will take to finish all the given tasks.

中譯

給定一個字串的陣列用來表示CPU要處理的工作。我們利用A-Z來表示各種不一樣的工作。工作完成的順序可以不依在陣列中的順序。每個工作須花費一個單位時間完成。每個單位時間，CPU可以選擇完成一件工作或是閒置。

我們用一個非負整數n來代表兩個相同工作中需要的間隔時間，也就是需要間隔個n 個單位時間。

你必須回傳CPU完成所有工作所需的最短時間。

範例

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints:

• The number of tasks is in the range [1, 10000].
• The integer n is in the range [0, 100].

解析

首先我們會先用一個map 去記錄每個工作出現的次數，不失一般性我們可以假設出現的次數是 A ≥ B ≥ C ≥ …，那我們可以先用A去隔出空格，如下

# suppose n = 2, A 出現三次是最多次的工作
A -> _ -> _ -> A -> _ -> _ -> A

我們依照出現次數依序放入空格中，這樣我們便可以完成排完工作了。

但這個排法會有個corner case，也就是工作太多了，放在隔出來的空格都放不完。但這種情況不難，我們只需要把多的工作，平均的放在每兩個A 的中間即可，這樣也同時能保證工作之間間格的時間是夠多的。

程式

Python