目录

一，题目描述

英文描述

中文描述

示例与说明

二，解题思路

三，AC代码

Java

四，解题过程

第一博

第二搏

一，题目描述

英文描述

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

中文描述

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

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

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

示例与说明

示例 1：

示例 2：

  
示例 3：

 

提示：

1 <= task.length <= 104
tasks[i] 是大写英文字母
n 的取值范围为 [0, 100]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/task-scheduler
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

以下图片均来自@popopop【【任务调度器】C++ 桶子_配图理解】。和官方最优题解差不多，但是解释的更加通俗易懂。

第一种情况：冷却时间未被占满

 第二种情况：冷却时间全部占满

三，AC代码

Java

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] record = new int[26];             // 任务名称为26个大写英文字母
        for (char c : tasks) record[c - 'A']++;
        int maxTask = 0;                        // 同类型任务的最大任务个数
        int numOfMaxTask = 0;                   // 满足任务个数最大的任务种类
        for (int i = 0; i < 26; i++) {
            if (record[i] > maxTask) {
                maxTask = record[i];
                numOfMaxTask = 1;
            } else if (record[i] == maxTask) {
                numOfMaxTask++;
            }
        }
        return Math.max(tasks.length, (maxTask - 1) * (n + 1) + numOfMaxTask);
    }
}

四，解题过程

第一博

乍一看不就是填充空缺吗，但是越看越不对劲，从一维的角度看任务不断叠加，不好看出其中的规律，而且漏掉了一个重要的条件：冷却时间至少为n，也就是说比n大也满足条件。 

所以没找到好的思路，第一波冲锋以失败告终。

第二搏

我对大佬的仰慕之情犹如滔滔江水，绵绵不绝~~~