leetcode621. 任务调度器

LeetCode系列文章

一、题目描述

  给你一个用字符数组 $tasks$ 表示的CPU需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU可以完成一个任务，或者处于待命状态。
 
  然而，两个相同种类的任务之间必须有长度为整数 $n$ 的冷却时间，因此至少有连续 $n$ 个单位时间内CPU在执行不同的任务，或者在待命状态。
 
  你需要计算完成所有任务所需要的最短时间。

二、示例

  输入： tasks = [‘A’, ‘A’, ‘A’, ‘B’, ‘B’, ‘B’], n = 2
  输出： 8
 
  解释： A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
 
  注意：任务都是用大写英文字母表示的。

三、主体思路

  要根据任务列表计算出完成所有任务所需要的最短时间，首先我们需要找到该任务列表当中所需执行次数最多的任务，然后以该任务为时间线进行分析。

  假设所给任务列表当中所需执行次数最多的是任务A，那么我们可以用一个矩阵来展现执行任务A的时间点。由于CPU执行相同种类的任务之间必须至少有长度为 $n$ 的冷却时间，为了让冷却时间最短，该矩阵的宽度就应该设置为 $n+1$，而该矩阵的高度就是任务A所需执行的次数。

  如果任务列表当中只有任务A，那么该矩阵中除了执行任务A的位置之外，其他位置所对应的就是 “待命状态”，并且当执行完最后一个任务A时，所有任务就都已经执行完毕了，因此矩阵最后一行当中剩下的 $n-1$ 位置此时不算入完成任务的所需时间（下图中用 ╳ 表示）。

  此时完成所有任务所需的时间就是：$(MaxExec-1)\times (n+1)+1$

  如果任务列表当中除了任务A之外还有其他种类的任务，那么这些任务就可以添加到图中 “待命状态” 的位置，如果这些任务能够全部被安排在 “待命状态” 当中，那么此时完成所有任务所需的时间与之前是相同的。

  任务A是所需执行次数最多的任务，因此不会有比任务A所需执行次数更多的任务，但我们无法保证没有所需执行次数与任务A相同的任务。如果出现了这种情况，我们就需要在矩阵的最后一行添加位置来执行该任务。

  因此，如果任务列表当中所需执行次数等于 $MaxExec$ 的任务个数为 $num$，那么完成所有任务所需的时间就是：$(MaxExec-1)\times (n+1)+num$

  现在我们就是将其他种类的任务添加到矩阵当中 “待命状态” 的位置，如果该任务所需执行的次数与 $MaxExec$ 相等，那么我们需要在矩阵的最后一行添加对应的位置。但如果矩阵当中的 “待命状态” 的位置都被填满了呢？此时任务列表当中剩余的任务应该怎么办？

  此时我们可以将矩阵中某些行的宽度进行扩充，然后将任务插入到这些扩展的位置当中即可。因为在矩阵没有扩充时，矩阵中同种任务之间执行的间隔时间恰好是 $n$，既然现在矩阵当中 “待命状态” 的位置被填满了，那么我们可以直接将剩下的任务插入到矩阵的行后面，插入后原矩阵当中的任务没有违反 “同种任务之间执行的间隔时间至少是 $n$ ” 的规定，并且新插入的任务也是满足冷却要求的。

  因此，如果任务列表当中所需执行任务的总数大于我们计算得到的矩阵的大小，那么此时完成所有任务所需的时间就是任务列表当中任务的个数。

四、代码实现

虽然该题目的思路比较复杂，但要将该思路落实到代码上其实还是很简单的。

1. 统计任务列表中每种任务出现的次数。（由于任务都是用大写字母表示的，因此只需用一个大小为26的vector容器进行存储即可）
2. 将各个任务按出现次数从多到少进行排序。（此时vector当中的第0个值就是 $MaxExec$ 的值）
3. 统计出现次数等于最多出现次数的任务个数。
4. 将计算得到的值与所需执行任务的总数进行比较，返回较大值。

代码如下：