LeetCode 621. 任务调度器***

具体思路：

个人最先开始还以为是简单的模拟；

看了题解才知道这是贪心模拟；

两种做法：

1. 贪心模拟；
2. 采用数值分析进行填充；

1.贪心模拟：

贪心模拟每次选择剩余个数最多的任务；

这里注意下题解模拟的写法，没有逐步计时，而是直接记录每个任务可执行的时间点，从而进行时间跳跃；

2.数值分析；

这里有点类似于之前遇到的组合字符让其两两不相邻的情况；

只不过换成了，每两个字符必须要中间至少有两位不一样；

如果n=2；

则统计最大字符个数，对剩余的字符进行插空；

如果不足，则插空字符；

如果最大字符个数为n；

则可以想象，有n-1个空位，当字符数不足时，可以填充空字符，所以总字符数为(n-1)*2+n=(n-1)*3+1；

如果字符个数够多，则无论怎么填充，都可以保证每两位不一样；

所以直接去(n-1)*3+1和tasks的数目的最大值即可；

具体代码： 1.贪心模拟：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        map<char,int>fre;
        for(auto& ch:tasks){
            fre[ch]++;
        }
        int m=fre.size();
        vector<int> nextVaild(m,1);
        vector<int> rest;
        for(auto it=fre.begin();it!=fre.end();it++)
            rest.push_back(it->second);
        int time=0;
        for(int i=0;i<tasks.size();i++){
            time++;
            int cur=INT_MAX;
            for(int j=0;j<m;j++){
                if(rest[j])
                    cur=min(cur,nextVaild[j]);
            }
            time=max(cur,time);
            //找到最小的时间，不用模拟，直接跳到该时间；
            int maxn=0;
            int index=-1;
            for(int j=0;j<m;j++){
                //寻找该时间下剩余任务数最多的；
                if(rest[j]==0)
                    continue;
                if(nextVaild[j]<=time&&rest[j]>maxn){
                    index=j;
                    maxn=rest[j];
                }
            }
            rest[index]--;
            nextVaild[index]=time+n+1;
        }
        return time;
    }     
};

具体代码： 1.贪心模拟： 2.数值分析：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        map<char,int>fre;
        int maxn=0;
        for(auto& ch:tasks){
            fre[ch]++;
            maxn=max(maxn,fre[ch]);
        }
        int maxcount=0;
        for(auto it=fre.begin();it!=fre.end();it++){
            if(it->second==maxn)
                maxcount++;
        }
        return max(static_cast<int>(tasks.size()),(maxn-1)*(n+1)+maxcount);
    }     
};