讨论/《中级算法》 - 任务调度器/
《中级算法》 - 任务调度器
共 3 个回复

题目解读与公式推导

题目解读:
字母代表不同的任务,给定的n是任务的延迟时间。
那么这个延迟时间是个什么意思呢?根据题目的描述此延迟时间的含义是:完成一个任务后如果还想继续完成相同的任务则需要n的延迟时间。举个例子--n = 2,如果此时我完成了A任务,则还需要隔n=2的时间才能再次完成A任务,所以A后面可以接B或者C,同样对B和C也是如此需要隔这么长的时间。

转自讨论区热评
数学公式推导:(count[maxSize] - 1) * (n + 1) + maxCount

  • 假设数组 ["A","A","A","B","B","C"],n = 2,A的频率最高,记为count = 3,所以两个A之间必须间隔2个任务,才能满足题意并且是最短时间(两个A的间隔大于2的总时间必然不是最短),因此执行顺序为: A->X->X->A->X->X->A,这里的X表示除了A以外其他字母,或者是待命,不用关心具体是什么,反正用来填充两个A的间隔的。上面执行顺序的规律是: 有count - 1个A,其中每个A需要搭配n个X,再加上最后一个A,所以总时间为 (count - 1) * (n + 1) + 1
  • 要注意可能会出现多个频率相同且都是最高的任务,比如 ["A","A","A","B","B","B","C","C"],所以最后会剩下一个A和一个B,因此最后要加上频率最高的不同任务的个数 maxCount
  • 公式算出的值可能会比数组的长度小,如["A","A","B","B"],n = 0,此时要取数组的长度

(cpp)解题代码

class Solution {
public:
//根据数学公式得出结果:(count[25] - 1) * (n + 1) + maxCount
    int leastInterval(vector<char>& tasks, int n) {
        int size = tasks.size();
        int hash[26];
        memset(hash,0,sizeof(hash));
        int maxSize = 0;
        //求出出现的最高次数
        for(char t:tasks){
            hash[t-'A']++;
            maxSize = max(maxSize,hash[t-'A']);
        }int maxCount = 0;
        //求出现最高次的频率
        for(int i=0;i<26;i++){
            if(hash[i]==maxSize)
                maxCount++;
        }
        int res = (maxSize-1)*(n+1)+maxCount;
        //一旦出现res小于数组长度,答案就为数组长度
        return res>=size?res:size;
    }
};
    public int leastInterval(char[] tasks, int n) {
        int[] ints = new int[26];
        //把所有值放入数组中
        for (int i = 0,len = tasks.length; i < len; i++) {
            ints[tasks[i] - 'A']++;
        }
        Arrays.sort(ints);

        //最后一行的个数
        int mod = 1;
        //一共多少行
        int everyLine = ints[25];
        for (int i = ints.length-1; i > 0 ; i--) {
            if(ints[i]==ints[i-1]) {
                mod++;//如果其他数跟最多的一样多,最后一行的个数+1
            }else{
                break;
            }
        }
        int res = (everyLine - 1) * (n + 1) + mod;
        
        return Math.max(res,tasks.length);
    }

看不懂