LeetCode 621. Task Scheduler

621. Task Scheduler
一、問題の説明
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals 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.

Note:

The number of tasks is in the range [1, 10000].

The integer n is in the range [0, 100].

三、問題を解く構想
欲張りアルゴリズム

は、1回のスケジューリングをn+1の長さのループと見なすことができる.cycle = n + 1. このcycleピットの場合は、異なるtaskで記入する必要があります.こんなに多くの種類のtaskがなければ、残りのピットcpuは

しか空転できません.

ピットを埋めるときにどのtaskを使うのか、できるだけ出現回数の多いtaskを使うようにします.taskは繰り返しられないので、できるだけ他のtaskを使って出現回数の最も多いtaskを隔てる必要があります.そうしないと、idleで隔てる必要があります.

アルゴリズムの考え方は、まずtaskごとに出現した回数を記録し、これらの回数をpriority_に記録することである.Queueでは、回数を知るだけでいいのでtaskの名前は気にしないでください.priority_Queueはデフォルトでは大きなトップスタック、すなわち出現回数の多いtaskが先にキューを出ます.毎回遍歴するたびに、私たちはpqの中のtaskをすべてキューから出して、もしこの時cycleが満たされたら、taskが現れた回数を全部1減らしてpqに追加して、総運行時間はcycle個のcpu運転周期を必要とします;cycleが満たされていない場合は、idleの一部を補充してピットを埋める必要があることを示し、運転時間は同様にcycleのcpu運転サイクルを増加させる.

ここで注意すべき点は,(1)taskの出現回数をpqに追加する場合,このラウンドで1つのtaskを使用した後,そのtaskの残り回数が0であるかどうかを判断する必要があり,0であれば追加できなくなり,スケジューリングが完了したことを示す.(2)このcycleが完了した後、taskがpqに再追加されていないことが判明した場合、すべてのtaskがスケジューリング済みであることを示し、今回のスケジューリングが最後である場合、cycleのCPU運転サイクルではなく実際のスケジューリング時間を追加するだけである.

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
                map<char, int> m;
        for (int i = 0; i < tasks.size(); ++i) {
            m[tasks[i]]++;
        }
        priority_queue<int> pq;
        for (auto ite : m){
            pq.push(ite.second);
        }
        int cycle = n + 1, ret = 0;
        while(!pq.empty()){
            vector<int> tmp;
            int time = 0;
            for (int i = 0; i < cycle; ++i) {
                if (!pq.empty()){
                    tmp.push_back(pq.top());
                    pq.pop();
                    time++;
                }
            }

            for (auto cnt : tmp){
                int remainCnt = cnt - 1;
                if(remainCnt > 0)pq.push(remainCnt);
            }
            if(pq.empty()) ret += time;//         ，    idle   
            else ret += cycle;
        }
        return ret;
    }
};