621. Task Scheduler

Question: Task Scheduler

Solution

想法：

1. 目標：在最短的時間內處理完所有的 Task
2. 處理相同的 Task 中間有冷卻時間，冷卻時間都一樣
3. Task 要從多的開始處理，才能有最少的時間
1. 假設 tasks = [A, A, A, B, B, C, C], n = 2
   1. A3, B2, C2, A 多所以先放 A → Ａ
   2. 此時 A2, B2, C2, 因為 ABC 數量都一樣，但 A 在冷卻時間，所以只能放 B or C 假設先放 B → Ａ B
   3. 此時 A2, B1, C2, A, C 數量都一樣，但 A B 在冷卻間，所以放 C → Ａ B C
   4. 此時 A2, B1, C1, A 最多，A 也可以放了，所以放 A → Ａ B C A
   5. 此時 A1, B1, C1, A, B, C 數量一樣，但 A, C 都在冷卻時間 所以放 B → Ａ B C A B
   6. 此時 B 放完了，不用再考慮，而 A1, C1，但 A 在冷卻時間 因此放 C → Ａ B C A B C
   7. 此時 C 放完了，不用再考慮， 剩 A，因此放 A → Ａ B C A B C A
2. 由上述可知，我們需要

1. 一個可以快速找到哪 Task 剩最多的 data structure → Max Heap

   但 python 中沒有 Max Heap，所以需要用 min Heap 做改良，將所有儲存的值加上負號，就變成 Max Heap 了。

   1. 把 Tasks 掃過一遍，個數記起來，所以要做成字典。 O(n) actually O(26)
   2. 製成 min Heap, heapq.heapify O(n), actually O(26)

2. 時間軸： time，每跑一輪就 + 1

3. 如果 min Heap 裡有東西，就 pop 出來 O(logn) actually O(log 26)

4. pop 出來的 task 少 1，如果歸 0 了就不處理，如果沒歸零就要記錄起來

5. 因此需要一個可以記錄冷卻時間的 data structure，欲儲存的資料是 Task 的數量與 Task 可以釋出的時間點，[Task left, release time]，按照冷卻時間的想法，先進的最快冷卻 → deque，先進先出 O(1)

6. 每跑完一輪就要檢查 deque 是否有現在時間可以取出的 task，放回 min Heap 裡 heapq.heappush(min heap, task) O(log n * 冷卻時間) actually O(log 26 * 冷卻時間)

from collections import deque, defaultdict

import heapq

class Solution:

def leastInterval(self, tasks: list[str], n: int) -> int:

q = deque()

task_num = defaultdict(int)

for _ in tasks:

task_num[_] += 1

min_heap = [-v for v in task_num.values()]

heapq.heapify(min_heap)

time = 0

while min_heap or q:

time += 1

if min_heap:

task = heapq.heappop(min_heap) + 1

if task < 0:

q.append([task, time + n])

if q and q[0][1] <= time:

ele, _ = q.popleft()

heapq.heappush(min_heap, ele)

return time

Video Solution