ปัญหา
กำหนด tasks list (ตัวเลข = task type) และ cooldown k
แต่ละ task ใช้ 1 นาที ต้องรอ k นาทีระหว่าง task ประเภทเดียวกัน
หาเวลาน้อยที่สุดทำให้เสร็จทั้งหมด
ตัวอย่าง: tasks=[2,2,2,3,3,2], k=1 → 7 นาที
Optimal: [2, 3, 2, 3, 2, WAIT, 2]
วิธีแก้: Greedy + Max Heap (Priority Queue)
ทุกๆ รอบ เลือก task ที่เหลือมากที่สุด (most frequent) จนกว่า cooldown จะหมด
อัลกอริทึม
- นับความถี่แต่ละ task → Counter
- วนจนกว่า Counter ว่าง:
- ดึง (k+1) task ที่ frequent ที่สุด
- ลด count แต่ละตัวลง 1, ลบออกถ้าเหลือ 0
- เพิ่มเวลา k+1
- ปรับผลลัพธ์สุดท้าย: ans + last_size - (k+1)
โค้ด Python
from collections import Counter
class Solution:
def solve(self, nums, k):
c = Counter(nums)
ans = 0
last_size = 0
while c:
last_size = len(c)
for x, _ in c.most_common(k + 1):
c[x] -= 1
if c[x] == 0:
del c[x]
ans += k + 1
return ans + last_size - (k + 1)
# ทดสอบ
ob = Solution()
print(ob.solve([2, 2, 2, 3, 3, 2], 1)) # 7
print(ob.solve([1, 1, 1, 1], 2)) # 10 (1, _, _, 1, _, _, 1, _, _, 1)
print(ob.solve([1, 2, 3], 2)) # 3 (no cooldown needed)
ความซับซ้อน
- Time: O(n log m) - m = unique tasks, most_common ใช้ heap
- Space: O(m) - counter storage
การทำงานตัวอย่าง [2,2,2,3,3,2], k=1
Round 1: c={2:4, 3:2}, most_common(2)=[(2,4),(3,2)]
Process 2,3 → c={2:3, 3:1}, ans=2
Round 2: most_common(2)=[(2,3),(3,1)]
Process 2,3 → c={2:2}, ans=4
Round 3: most_common(2)=[(2,2)]
Process 2 → c={2:1}, ans=6
Round 4: most_common(2)=[(2,1)]
Process 2 → c={}, last_size=1, ans=8
Return: 8 + 1 - 2 = 7
ความสัมพันธ์กับ LeetCode 621
นี่คือโจทย์ "Task Scheduler" (LeetCode 621) - รูปแบบคลาสสิกของ greedy scheduling
