前往
大廳
主題

LeetCode - 0621. Task Scheduler 解題心得

Not In My Back Yard | 2023-07-01 12:00:04 | 巴幣 0 | 人氣 156

題目連結:


題目意譯:
給定一個字元陣列 tasks,代表著一個 CPU 需要做的工作,其中每一種字母代表著不同的工作。這些工作可以按照任意順序做。每一個工作只需要一單位時間便可以完成。對於每單位的時間,CPU 可以完成一件工作或是閒置。

不過,現在有一個非負整數 n 其代表著兩個相同工作(陣列中的相同字母)之間的冷卻時間,也就是說在任意兩個相同工作之間必須間隔至少 n 單位的時間。

回傳 CPU 完成所有給定的工作最少所需的單位時間。

限制:
1 ≦ task.length ≦ 10 ^ 4
tasks[i] 為大小英文字母。
整數 n 位於範圍 [0, 100] 中。



範例測資:
範例 1:
輸入: tasks = ["A","A","A","B","B","B"], n = 2
輸出: 8
解釋:
A → B → idle → A → B → idle → A → B
每兩個相同工作之間至少有 2 單位的時間。

範例 2:
輸入: tasks = ["A","A","A","B","B","B"], n = 0
輸出: 6
解釋: 在此例中,任意大小為 6 的排列都是可行的,因為 n = 0。
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
以此類推。

範例 3:
輸入: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
輸出: 16
解釋:
其中一個可能的解法為
A → B → C → A → D → E → A → F → G → A → idle → idle → A → idle → idle → A


解題思維:
(假設總工作數為 t,即 t = tasks.length)
如果 n = 0,則所求即為 t。

反之,找出哪種工作是數量最多的(如果有多個最多,則稱呼這些工作的數量為 C),稱其數量為 M。可以看到我們可以把數量最多的工作當作「隔板」來使用,例如說現在 A 這種工作很多,而 n = 2,則我們可以得到:
A__A__A__A……
其中「_」代表著可以安放其他工作的位置,或是單純閒置。而這個長度將會是 (n + 1) × (M - 1) + 1,而如果有多個數量最多的工作,則為 (n + 1) × (M - 1) + C。

因此我們可以把其他工作安放在這些「_」上。而如果沒有「_」可以放時,則我們需要延展這些「隔板」之間的空位來放,而此時實際上答案為 t。

因此答案為 max(t, (n + 1) × (M - 1) + C)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作