###### tags: `Leetcode` `medium` `hash` `heap` `python` `c++`

# 621. Task Scheduler

## [題目連結] https://leetcode.com/problems/task-scheduler/description/

## 題目:
Given a characters array ```tasks```, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. 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.

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

**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

## 解題想法:
* 此題為對於很多task進行CPU調用計算，同樣的task之間的時間間格不可少於n，否則用idle填充，求最少時間處理所有task

* 法1:公式解
* ex: tasks=AAABBBCC, n=2
* countA=3
* countB=3
* countC=2
* 因為相同的一定要有間格2
* 所以先放出現最多的(A、B)
* 放法:
* (AB)視為一組:可以分為
* **countA-1**組: 每組時間為(n+1)
* **1組**尾巴組: 不用再補idle於後面

        A B _
        A B _
        A B

* 可推算總時間為: **(最多任務次數-1)*( n+1 )+相同最多任務的任務個數(即尾巴)**

## Python: 公式解

from collections import Counter
class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        counter=Counter(tasks)
        #由大到小 收集value即可
        collect=sorted(counter.values(), reverse=True)
        most=collect[0]
        #求尾巴 取相同最長的val有幾個
        numOfMost=collect.count(most)
        max_len=(most-1)*(n+1)+numOfMost
        return max(len(tasks), max_len)

# 需要與最大值進行比較
# 因為ex: tasks=[A,A,A,B,B,B], 0
# 公式解為: (3-1)*(0+1)+2=4
# 但每個任務皆須遍歷!
    
result=Solution()
tasks = ["A","A","A","B","B","B","C","C"]
n = 2
ans=result.leastInterval(tasks,n)
print(ans)

* 法2: heap_queue
* 每輪有(n+1)的時間
* 優先把最多次數的任務加入queue
* 依序pop出n+1個任務表示該輪結束
* 將pop的任務次數-1並再加入queue
* 重複直到所有任務次數為0

## C++: Priority_queue

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> dic;
        for (char item: tasks){
            dic[item]+=1;
        }
        priority_queue<int> que; //max_heap
        for (auto item: dic){ //key: dic.first; value: dic.second
            que.push(item.second);
        }
        int totalCost=0, cycle=n+1;
        while (!que.empty()){
            int curTime=0;
            vector<int> nextCycle;
            for (int i=0; i<cycle; i++){
                if (!que.empty()){
                    int curNum=que.top(); que.pop();
                    if (curNum-1!=0){ //次數減一仍大於0，可以加入下一輪
                        nextCycle.push_back(curNum-1);
                    }
                    curTime+=1;
                }
            }
            //將下輪加入到queue
            for (int item: nextCycle) que.push(item);
            //若que還沒空，表示此輪安全跑完整趟n+1個任務
            //若que空，表示此輪為最後一輪了，則加上curTime即可不用補idle
            totalCost+= (!que.empty()) ? cycle: curTime;
        }
        return totalCost;
    }
};