leetcode Task Scheduler java

题干

给定一个用字符数组表示的 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, 10000]。
n 的取值范围为 [0, 100]。

想法

贪心算法，我们需要了解这样一个事实：
如果按照出现频率来调度，那么是一定满足冷却时间的。假设冷却时间为p，那么每p+1个时间为一组是能调度出来的。
也就是说我们用p个位置将两个最高频的数分开，最高频的尚且刚好满足冷却时间，其他的出现频率肯定没有最高频的高，所以也肯定满足。
举个例子：
AAACCD 2
A–A--A
AC-AC-A
ACDAC-A
满足题意显然。

这就是第一种方法：

第一种方法由于效率低下，如果if 后边的{}也写完整会超时！注意注意

方法一代码

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        //map记录频次
        for (char c: tasks)
            map[c - 'A']++;
            //排序，注意频次最高的在最后
        Arrays.sort(map);
        int time = 0;
        while (map[25] > 0) {//最大数还没安排完
            int i = 0;//一轮有n+1个位置
            while (i < n+1) {
                if (map[25] == 0)
                    break;
                if (i < 26 && map[25 - i] > 0)//次大的
                    map[25 - i]--;
                time++;
                i++;
            }
            Arrays.sort(map);//重新排序
        }
        return time;
    }
}

复杂度分析

时间复杂度：O(\text{time})O(time)，由于我们给每个任务都安排了时间，因此时间复杂度和最终的答案成正比。

空间复杂度：O(1)O(1)。

方法二

在前两种方法中，我们了解到应当尽早安排出现次数较多的任务。我们假设 A 为出现次数最多的任务，假设其出现了 p 次，考虑到冷却时间，那么执行完所有任务的时间至少为 (p - 1) * (n + 1) + 1。我们把这个过程形象化地用图 1 表现出，可以发现，CPU 产生了 (p - 1) * n 个空闲时间，只有 p 个时间是在工作的。

因此我们应当考虑把剩余的任务安排到这些空闲时间里，我们仍然按照这些任务的出现次序，从大到小进行安排，会有下面三种情况：

某个任务和 A 出现的次数相同，例如图 2 中的任务 B。此时我们只能让 B 占据 p - 1 个空闲时间，而在非空闲时间里额外安排一个时间给 B 执行；

某个任务比 A 出现的次数少 1，例如图 2 中的任务 C。此时我们可以让 C 占据 p - 1 个空闲时间，就可以全部执行完；

某个任务比 A 出现的次数少 2 或更多，例如图 2 中的任务 D。此时我们可以按照列优先的顺序，将 D 填入空闲时间中。因为 D 出现的次数少于 p - 1，因此无论从哪个位置开始按照列优先的顺序放置，都可以保证相邻的两个 D 之间满足冷却时间的要求。

在将所有的任务安排完成后，如果仍然有剩余的空闲时间，那么答案即为（任务的总数 + 剩余的空闲时间）；如果在安排某一个任务时，遇到了剩余的空闲时间不够的情况，那么答案一定就等于任务的总数。这是因为我们可以将空闲时间增加虚拟的一列，继续安排任务。如果不考虑这些虚拟的列，在原本空闲时间对应的那些列中的任务是可以按照要求顺序执行的，而增加了这些虚拟的列后，两个相邻的相同任务的间隔不可能减少，并且虚拟的列中的任务也满足冷却时间的要求，因此仍然顺序执行并跳过虚拟的列中剩余的“空闲时间”一定是可行的。

Java代码

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        for (char c: tasks)
            map[c - 'A']++;
        Arrays.sort(map);
        int max_val = map[25] - 1, idle_slots = max_val * n;
        for (int i = 24; i >= 0 && map[i] > 0; i--) {
            idle_slots -= Math.min(map[i], max_val);
        }
        return idle_slots > 0 ? idle_slots + tasks.length : tasks.length;
    }
}

复杂度分析

时间复杂度：O(M)O(M)，其中 MM 是任务的总数。

空间复杂度：O(1)O(1)。

博客代码想法参考https://leetcode-cn.com/problems/task-scheduler/solution/ren-wu-diao-du-qi-by-leetcode/ ，图片也来自于官方题解

总结

这题有内味儿了 有点费脑