LEETCODE 621. Task Scheduler 解题思路分析

发表于2019年4月11日由admin

题目大意：

任务调度器

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A – Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

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

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

示例 1：

输入: tasks = ["A","A","A","B","B","B"], n = 2 
输出: 8 
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

注：

  1. 任务的总个数为 [1, 10000]。
  2. n 的取值范围为 [0, 100]。

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=621

解题思路：

这是一道中等难度的题目，难点在于我们如何推导出计算公式，简单的说一下思路。首先题目是要求给CPU分配任务，相同的任务不能连续执行，中间要有冷却时间。比如有三个相同的任务A，冷却时间为2，那么3个A任务全部执行完毕需要7个时间单位：

'A', '_', '_', 'A', '_', '_', 'A'

其中 ‘_’ 代表冷却时间，也就是题目中说的待命（idle）。在冷却时间内可以执行其他任务，但其他相同任务也要保持相同的冷却时间。

其实这很像一道填空题，我们先找到一个或多个数量最多的任务，将他们分成一组，然后再在他们执行的中间加上冷却时间，然后再将其他的任务添加到这些冷却时间里即可。不过，具体思考起来，会发现存在以下几种可能：

例1：这是一种最理想的情况，数量最多的任务A之间有2个冷却，那么把剩下的任务B加入到任意一个冷却中即可。

task = {'A','A','A','B'};
n = 1;

Result = {'A','B','A','_','A'} // length = 5

这种情况下，最终的最短执行时间就是数量最多的任务的执行时间，即：

length = count('A') + (count('A') - 1) * n

count(‘A’)是任务A的个数，(count(‘A’) – 1) * n是每个任务A之间所有的冷却个数。

例2：如果剩下的任务数大于冷却数呢？

task = {'A','A','A','B','B','C','C'};
n = 1;

同理，我们还是先安排数量最多的任务A：

Result = {'A','_','A','_','A'}

然后将之后的任务B加入到上面的冷却时间中：

Result = {'A','B','A','B','A'}

之后剩下任务C，任务该C如何插入？将剩下的2个C加到任务列表之后显然不是最优解，{‘A’,’B’,’A’,’B’,’A’,’C’,’_’,’C’}。这时，虽然A之间已经没有冷却时间，其实这并不妨碍我们将C插入其中间，所以，这时的最优解应该是：

Result = {'A','B','C','A','B','C','A'}

在这种情况下，最终的最短执行时间应该是，数量最多任务的执行时间（例1的公式）再加上 其他任务的总数与数量最多任务的冷却个数之差。

count = 数量最多任务的执行时间 + (其他任务的总个数 - 数量最多任务的冷却个数)

简单来说，就是将其他任务尽量填到数量最多的任务的执行空隙中，如果空填完了其他任务还有剩余，那么剩余这部分的数量也要加到结果中。

例3：这个例子是我在写代码时犹豫过的一个地方，后来想通之后，发现和例1是同一种情况。

task = {'A','A','A','B','B','C','C','D','D'};
n = 2;

首先还是先填空，将B和C填完之后的情况是：

{'A','B','C','A','B','C','A','_','_'};

这时剩下2个空和两个任务D，如果把D放到最后两个空上，显然不符合要求，这时该如何思考？仔细分析过，其实两个D还是可以放到A剩下的两个冷却中去，原因是，之前的B和C我们都放在了前两组空位中，如果调换一下位置，比如将第一个B放到最后一组空格中，这样，再把两个D分别放入第一和第三组中就能够保证冷却问题。即：

{'A','_','C','A','B','C','A','B','_'};

这时，再放D就不存在问题了。这样思考之后确定了关键的一点就是，只要还存在空位（冷却），我们就可以将剩下的任意一个任务放进去，如果空位填满之后还有剩余任务，就按照例2的逻辑去思考即可。

例4：最后一种情况。

之前一直提到一个前提，即先安排数量最多的任务，这样做的是为什么呢？原因很简单，我们要保证剩下的每种任务数量都要小于等于数量最多任务的冷却组数。比如有三个A，考虑到冷却，那么三个A之间必定要存在2组冷却，如果其他的任务个数都小于3，那么我们就可以保证将任务分别放入每组冷却中，避免同一任务不得不放入同一组的情况出现。举个例子，比如

task = {A, A, A, A, B ,B}
n = 1;

// 正确的做法，这时将2个B分别放入不同的两个空中即可
{A, _, _ , A, _, _, A, _, _, A} 

// 反之，4个A就不得不放入B的同一组空挡之中
{B, _, _ , B}

回到我们要讨论的最后一种情况，如果存在多个数量最多的任务时该如何处理？比如：

task = {A, A, A, B ,B, B, C, C}
n = 2;

这时，有3个任务A和3个任务B，我们可以将他们绑定为一组来思考，即：

task = {AB, AB, AB, C, C}

同时，A和B顺序绑定之后，又解决了一个冷却时间问题，我们需要将n减去1，这时安排数量最多的任务时应该为：

Result = {A, B, _, A, B, _, A, B} // 正确
而不是
Result = {A, B, _, _, A, B, _, _, A, B} // 错误

思路分析完了，看下完整代码：

public static int leastInterval(char[] tasks, int n) {
    int countArray[] = new int[26];
    // 循环出每个任务的数量
    for (char c : tasks) {
        countArray[c - 'A'] += 1;
    }
    // 将数量数组排序
    Arrays.sort(countArray);
    // 因为是正序排序，所以数组的最后一位即是，最多任务量
    int maxTaskCount = countArray[countArray.length - 1];
    int sameMaxTaskCountNum = 0; // 具有最多任务量的任务个数
    int otherTaskAllCount = 0; // 其他任务的总数
    for (int count : countArray) {
        if (count == maxTaskCount) {
            // 统计具有最多任务量的任务个数
            sameMaxTaskCountNum++;
        } else {
            // 统计其他任务的总数量
            otherTaskAllCount += count;
        }
    }
    // 根据最多任务量的任务个数来确定冷却的个数
    int blank = sameMaxTaskCountNum >= n + 1 ? 0 : (maxTaskCount - 1) * (n - (sameMaxTaskCountNum - 1));
    // 最多任务量的任务应占用的时间长度
    int maxTaskLength = maxTaskCount * sameMaxTaskCountNum + blank;
    // 将其他任务总数尽量填充到冷却中，剩余部分需额外占用时间
    int otherTaskLength = blank >= otherTaskAllCount ? 0 : otherTaskAllCount - blank;
    return maxTaskLength + otherTaskLength;
}

本解法耗时2ms。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-621-task-scheduler-解题思路分析/
此条目发表在leetcode分类目录，贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。