题目介绍

力扣621题：https://leetcode-cn.com/problems/task-scheduler/
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

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

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

分析

调度（Schedule）是操作系统的核心功能之一，保证多任务多线程的应用能够高效的利用硬件资源。本题就是模拟了操作系统中CPU任务调度的过程。

不同的任务可以依次执行，说明现在是单核CPU串行运作，同一时间只能执行一个任务。而同类型任务之间设置了冷却时间，主要也是为了保证各类型任务能够尽量均匀地占有CPU，不要出现长时间运行同一类任务的情况。

我们发现，由于任务是串行的，所以每个任务的执行时间不可能缩短，至少需要tasks.length个时间单位。而现在要想总执行时间最短，其实就是让额外的冷却时间最短。

方法一：模拟法

一种简单的想法是，我们按照时间顺序，依次给每一个时间单位分配任务。这就相当于我们模拟了一个CPU时钟。如果当前有多种任务可以执行，我们可以采用贪心策略：每次选择剩余执行次数最多的那个任务。这样将每种任务的剩余执行次数尽可能平均，就可以使得 CPU 处于待命状态的时间尽可能少。

具体实现上，我们可以定义两个状态列表，分别保存每个任务当前剩余的个数，以及最早可执行的时间。然后可以设置一个循环，模拟时间time不停向前推进。
具体执行过程：

• 首先遍历还没做完任务，找到可执行时间最早的那个；
• 然后判断时间time是否到了，如果还没到，直接推进到执行任务的时间；
• 由于有可能当前时间time，已经超过了多个任务的最早可执行时间，所以我们还要遍历这些任务，找到可执行次数最多的那个；
• 执行任务，更新状态

代码如下：

// 方法一：模拟法
public int leastInterval1(char[] tasks, int n){
    // 用HashMap统计每个任务出现的次数
    HashMap<Character, Integer> countMap = new HashMap<>();
    for (char task: tasks)
        countMap.put(task, countMap.getOrDefault(task, 0) + 1);

    // 任务种类数量
    int t = countMap.size();

    // 定义两个状态列表
    ArrayList<Integer> restCount = new ArrayList<>(countMap.values());    // 任务剩余次数
    ArrayList<Integer> nextAvailableTime = new ArrayList<>(Collections.nCopies(t, 1));    // 任务下次可执行时间

    int time = 0;    // 模拟CPU时钟

    // 遍历任务选择执行
    for (int i = 0; i < tasks.length; i++){
        time ++;

        int minNextAvailableTime = Integer.MAX_VALUE;
        // 1. 获取所有任务中最早可执行的时间
        for (int j = 0; j < t; j++){
            // 取还没做完的任务
            if (restCount.get(j) != 0){
                minNextAvailableTime = Math.min(minNextAvailableTime, nextAvailableTime.get(j));
            }
        }

        // 2. 直接推进时间，执行任务
        time = Math.max(time, minNextAvailableTime);

        // 3. 选取可执行任务中，剩余次数最多的那个执行
        int maxRestCountTask = -1;    // 保存要执行任务的索引
        for (int j = 0; j < t; j ++){
            if (restCount.get(j) > 0 && nextAvailableTime.get(j) <= time){
                // 如果比之前保存的最大剩余任务数还大，就更新
                if (maxRestCountTask == -1 || restCount.get(j) > restCount.get(maxRestCountTask)){
                    maxRestCountTask = j;
                }
            }
        }

        // 4. 执行任务，更新状态列表
        nextAvailableTime.set(maxRestCountTask, time + n + 1);
        restCount.set(maxRestCountTask, restCount.get(maxRestCountTask) - 1);
    }

    return time;
}

复杂度分析

• 时间复杂度：O(N ⋅∣Σ∣)，其中N是数组tasks的长度，∣Σ∣是数组tasks 中出现任务的种类。在对time 的更新进行优化后，每一次遍历中我们都可以安排执行一个任务，所以总共进行n 次遍历，每次遍历的时间复杂度为O(∣Σ∣)，相乘即可得到总时间复杂度。
• 空间复杂度：O(∣Σ∣)。我们需要使用哈希表统计每种任务出现的次数，以及使用两个状态列表帮助我们进行遍历得到结果，这些数据结构的空间复杂度均为O(∣Σ∣)。

方法二：构造法

这种思路比较巧妙，我们可以构造一个二维矩阵，来可视化地表示每个任务执行的时间点。

我们首先考虑所有任务种类中，执行次数最多的那一类任务，记它为A，其执行次数为 maxCount。

我们使用一个宽为 n+1 的矩阵，可视化地展现执行任务A 的时间点。矩阵中任务是逐行顺序执行的，没有任务的格子对应 CPU 的待命状态。这里宽度定为n+1的目的，就是因为冷却时间为 n，我们只要将所有的 A 全部填入矩阵的第一列，就可以保证满足题目要求。

而且容易看出，如果只有A任务，这就是可以使得总时间最小的排布方法，对应的总时间为：
(maxCount−1)·(n+1) + 1

同理，如果还有其它也需要执行maxCount次的任务，我们也需要将它们依次排布成列。例如，当还有任务B和C时，我们需要将它们排布在矩阵的第二、三列。

果需要执行 maxCount次的任务的总数量为maxNum，那么类似地可以得到对应的总时间为：
(maxCount −1)·(n+1) + maxNum

处理完执行次数为maxCount次的任务，剩余任务的执行次数一定都小于 maxCount，那么我们应当如何将它们放入矩阵中呢？
一种构造的方法是，我们从倒数第二行开始，按照反向列优先的顺序（即先放入靠左侧的列，同一列中先放入下方的行），依次放入每一种任务，并且同一种任务需要连续地填入。例如还有任务D，E 和F 时，我们会按照下图的方式依次放入这些任务。

对于任意一种任务而言，一定不会被放入同一行两次，间隔时间一定达到了n。因此如果我们按照这样的方法填入所有的任务，那么就可以保证总时间不变，仍然为：(maxCount −1)·(n+1) + maxNum

代码如下：

// 方法二：构造法
 public int leastInterval(char[] tasks, int n){
     // 用HashMap统计每个任务出现的次数
     HashMap<Character, Integer> countMap = new HashMap<>();
     for (char task: tasks)
         countMap.put(task, countMap.getOrDefault(task, 0) + 1);

     // 任务种类数量
     int t = countMap.size();

     int maxCount = 0;
     int maxNum = 0;

     // 1. 计算maxCount
     for (int count: countMap.values()){
         maxCount = Math.max(maxCount, count);
     }

     // 2. 计算maxNum
     for (char task: countMap.keySet()){
         if (countMap.get(task) == maxCount)
             maxNum ++;
     }

     // 3. 按照公式直接返回
     return Math.max(tasks.length, (maxCount - 1) * (n + 1) + maxNum);
 }

杂度分析

• 时间复杂度：O(N +∣Σ∣)，其中N是数组tasks的长度，∣Σ∣是数组tasks
  中出现任务的种类，在本题中任务都用大写字母表示，因此∣Σ∣不会超过 26。
• 空间复杂度：O(∣Σ∣)。