力扣题621. 任务调度器-------cpu调度轮转

题目：

这道题可以看成电脑里面的cpu时间片轮转，也就是给你一堆任务，一个时间片能处理n个，问你最少需要多少个时间片？（这里计算秒数）

思路：

• 由于是求最少的秒数，那么我们肯定能想到先把任务数最多的先执行，这样才能得到最佳的答案，在这里我们就可以用优先队列去做，先把所有的任务数的个数放进队列中（在此之前先for循环记录下各类任务的个数），在根据题目中的n去执行队列中的数字的出队，这里要用一个vector记录出队后的任务数（出队后任该务类的个数还有就放进vector）,然后再把vector里的元素重新放进队列中。

• 第二种方法比较巧妙

  • 将任务按类型分组，正好A-Z用一个int[26]保存任务类型个数
  • 对数组进行排序，优先排列个数（count）最大的任务，如题得到的时间至少为 retCount =（count-1）* (n+1) + 1 ==> A->X->X->A->X->X->A(X为其他任务或者待命)
  • 再排序下一个任务，如果下一个任务B个数和最大任务数一致，则retCount++ ==> A->B->X->A->B->X->A->B
  • 4、如果空位都插满之后还有任务，那就随便在这些间隔里面插入就可以，因为间隔长度肯定会大于n，在这种情况下就是任务的总数是最小所需时间

代码一：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int mp[26]={0};
        for(auto i:tasks){
            mp[i-'A']++;
        }

        priority_queue<int> q;
        for(auto i:mp){
            if(i) q.push(i);
        }

        int time = 0;
        while(q.size()){
            vector<int> st;

            int i = 0;
            while(i<=n){
                if(q.size() && q.top()>1){
                    st.push_back(q.top()-1);
                    q.pop();
                }else if(q.size()){
                    q.pop();
                }
                ++time;
                if(q.size()==0 && st.size()==0) break;
                ++i;
            }
            for(int i=0;i<st.size();++i){
                q.push(st[i]);
            }
        }
        return time;
    }
};

代码二：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int mp[26]={0};
        for(auto i:tasks){
            mp[i-'A'] ++;
        }
        sort(mp,mp+26);
        int Max = mp[25];
        int count = (Max-1)*(n+1)+1;

        int i = 24;
        while(i>=0 && mp[i]==Max){
            ++count;
            --i;
        }

        return count>tasks.size() ? count : tasks.size() ;
    }
};