LeetCode 题解 - 621.Task Scheduler

题目链接： https://leetcode.com/problems/task-scheduler

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

Return the minimum number of intervals required to complete all tasks.

函数定义：

class Solution {
 public:
  int leastInterval(vector<char>& tasks, int n) {}
};

这是一道典型的贪心算法题目。容易想到，CPU 执行的最小时间取决于频率最高的任务 $Task_{f_{max}}$。

假设 $Task_{f_{max}}$ 的频率为 $f_{max}$，相同任务之间的间隔（interval）为 $n$，那么将 $Task_{f_{max}}$ 全部执行完需要的时间为： $$(f_{max}-1)\times(n+1) + 1$$ 其中 $f_{max}-1$ 是因为最后一个 $Task_{f_{max}}$ 执行完毕后不需要再添加 $n$ 个时间，只添加 $1$ 个时间即可。

此时产生的空位数量 $Slot = (f_{max}-1) \times n$。

假设 $Task_{f_{max}}$ 只有一个，那么剩余任务只需要全部放在两个 $Task_{f_{max}}$ 执行的间隙当中即可。假设剩余任务的数量为 $T$：

1. 有些情况下 $T < Slot$，例如当任务列表为 $AAABB$，$n=2$ 时，容易得到 $Slot = 4$ 而 $T = 2$。这种情况下的一种最小调度序列为 $AB-AB-A$。
2. 有些情况下 $T \geq Slot$，例如当任务列表为 $AAABBCCDE$，$n=2$ 时，容易得到 $Slot = 4$ 而 $T = 6$。这种情况下的一种最小调度序列为 $ABCDEABCA$​。

容易看出情况 1 时 $Slot$ 装得下剩余的任务，因此执行最小时间为 $(f_{max}-1)\times(n+1) + 1$；而情况 2 时 $Slot$ 不够用，需要在间隔（interval）当中加入超过 $Slot$​ 的任务，因此执行最小时间为 $tasks.size()$。因此执行最小时间的计算公式为： $$max((f_{max}-1)\times(n+1) + 1, tasks.size())$$ 值得注意的是，情况 2 下没有比加到间隔（interval）当中更优的调度方式。

但是，如果 $Task_{f_{max}}$ 有 $m$ 个，那么把所有任务都执行完需要的最小时间是多少呢？

相比 $Task_{f_{max}}$ 只有一个的情况，我们需要在调度序列最后添加更多的时间。

此时，每个 $Task_{f_{max}}$ 都首先消耗 $f_{max} - 1$ 个 $Slot$，在调度序列末尾，需要再消耗一个时间执行最后的 $Task_{f_{max}}$，即 $(f_{max}-1)\times(n+1) + m$。如果 $Slot$ 不足以 $Task_{f_{max}}$ 以及其他 $Task$ 消耗，执行最小时间仍然是 $tasks.size()$。因此执行最小时间的计算公式为： $$max((f_{max}-1)\times(n+1) + m, tasks.size())$$ 举例来说，如果 $tasks$ 为 $AAABBBC$，

• 若 $n = 1$ ，则

  1. 首先根据 $Task_{f_{max}}$ 找到 $Slot$ ：$A-A-A$；
  2. 继续令下一个 $Task_{f_{max}}$ 消耗 $Slot$：$ABABAB$，注意最后 $B$ 多消耗了一个时间；
  3. $Slot$ 不足以 $C$ 的消耗，因此执行最小时间为 $tasks.size() = 7$​。

• 若 $n=2$，则

  1. 首先根据 $Task_{f_{max}}$ 找到 $Slot$ ：$A--A--A$；

  2. 继续令下一个 $Task_{f_{max}}$ 消耗 $Slot$：$AB-AB-AB$，注意最后 $B$ 多消耗了一个时间；

  3. $Slot$ 足以 $C$ 的消耗，因此执行最小时间为 $(f_{max}-1)\times(n+1) + m = (3-1)\times(2+1)+2 = 8$。

把以上公式写成代码，就得到了题解：

class Solution {
 public:
  int leastInterval(vector<char>& tasks, int n) {
    const int TASK_COUNT = tasks.size();

    vector<int> taskFrequency(26, 0);
    int maxTaskFrequency = 0;
    for (char task : tasks) {
      taskFrequency[task - 'A']++;
      maxTaskFrequency = std::max(maxTaskFrequency, taskFrequency[task - 'A']);
    }

    const int taskWithMaxFrequencyCount =
        std::count_if(taskFrequency.cbegin(), taskFrequency.cend(),
                      [maxTaskFrequency](auto element) {
                        return element == maxTaskFrequency;
                      });

    return std::max(TASK_COUNT, (maxTaskFrequency - 1) * (n + 1) +
                                    taskWithMaxFrequencyCount);
  }
};