621. 任务调度器（高频题）

621. 任务调度器

• 解题思路
• 代码

解题思路

这题大致用贪心思想，但是我觉得这是一个找规律的题目。一刷2021/3/21，没弄明白

二刷 2021/4/29，其实就是求那个图的面积

详情见题解

不过要注意有多少个任务和出现最多的那个任务出现次数一样，必须要连续，否则那个正方形就拼不满，只能用冷却来补，这是不行的！

代码

class Solution {
/**
 * 解题思路：
 * 1、将任务按类型分组，正好A-Z用一个int[26]保存任务类型个数
 * 2、对数组进行排序，优先排列个数（count）最大的任务，
 *      如题得到的时间至少为 retCount =（count-1）* (n+1) + 1 ==> A->X->X->A->X->X->A(X为其他任务或者待命)
 * 3、再排序下一个任务，如果下一个任务B个数和最大任务数一致，
 *      则retCount++ ==> A->B->X->A->B->X->A->B
 * 4、如果空位都插满之后还有任务，那就随便在这些间隔里面插入就可以，因为间隔长度肯定会大于n，
 *      在这种情况下任务的总数是最小所需时间(由于这种情况时再用上述公式计算会得到一个不正确且偏小的结果，
 *      因此，我们只需把公式计算的结果和tasks的长度取最大即为最终结果。)
 */
    public int leastInterval(char[] tasks, int n) {
        if (tasks.length <= 1 || n < 1) {
            return tasks.length;
        }
        //步骤1
        int[] counts = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            counts[tasks[i] - 'A']++;
        }
        //步骤2
        Arrays.sort(counts);
        int maxCount = counts[25];//经过上轮排序后，出现次数最多的元素在数组末尾，也就是下标为25的地方
        int retCount = (maxCount - 1) * (n + 1) + 1;
        int i = 24;
        //步骤3
        while (i >= 0 && counts[i] == maxCount) {
            retCount++;
            i--;
        }
        //步骤4
        return Math.max(retCount, tasks.length);
    }
}

另一个版本的代码，方便理解

class Solution {
    public int leastInterval(char[] tasks, int n) {
    int[] buckets = new int[26];
    for(int i = 0; i < tasks.length; i++){
        buckets[tasks[i] - 'A']++;
    }
    Arrays.sort(buckets);
    //出现最多的元素的次数
    int maxTimes = buckets[25];
    //有多少个任务和出现最多的那个任务出现次数一样。默认为1，就是buckets[25]本身
    int maxCount = 1;
    for(int i = 25; i >= 1; i--){
        if(buckets[i] == buckets[i - 1]){
            maxCount++;
        }
        else{
            break;
        }
    }
    //根据图来理解就行了，这个其实就是求图的面积
    int res = (maxTimes - 1) * (n + 1) + maxCount;
    return Math.max(res, tasks.length);
}
}