任务调度器

题目

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

思路

1. 求出每个字母最大的数量
2. 将最大数量的字母依次放入
3. 计算当前的最后一行数量
4. 判断字母总数与容量的大小
5. 选出最大的最为结果

代码

int leastInterval(vector<char>& tasks, int n) {
    sort(tasks.begin(),tasks.end());
    int res = 0;
    if(n==0){
        return tasks.size();
    }
    else{
        /**
         * vector<int> index(tasks.size(),0); 报错：
         * AddressSanitizer: heap-buffer-overflow on address 0x602000000618 at pc 0x00000034e7a6 bp 0x7ffca92cbfd0 sp 0x7ffca92cbfc8
         *   READ of size 4 at 0x602000000618 thread T0
         */
        // 统计每个字母出现的次数
        vector<int> index(2*tasks.size(),0);
        index[0] = 1;
        int pre = 0;
        for(int i=1;i<tasks.size();i++){
            if(tasks[i-1]==tasks[i]){
                index[pre] = index[pre]+1;
            }else{
                pre++;
                index[pre]=1;
            }
        }
        // 对次数大小进行排序
        sort(index.rbegin(),index.rend());
        int maxnum = *max_element(index.begin(),index.end());
        int lastrow = 1;
        // 判断有几个相同的最大数
        for(int i=1;index[i]!=0&&i<=n;i++){
            if(maxnum == index[i]){
                lastrow += 1;
            }
        }
        // 选出最大值返回结果
        if(((n+1)*(maxnum-1)+lastrow)>tasks.size())
            res = (n+1)*(maxnum-1)+lastrow;
        else
            res = tasks.size();
    }
    return res;
}