[LeetCode] 621. 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.

Example 1:
Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two cycles before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th cycle, you can do A again as 2 intervals have passed.

Example 2:
Input: tasks = [“A”,”C”,”A”,”B”,”D”,”B”], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:
Input: tasks = [“A”,”A”,”A”, “B”,”B”,”B”], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:
1 <= tasks.length <= 104
tasks[i] is an uppercase English letter.
0 <= n <= 100

任务调度器。

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/task-scheduler
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题我给出两种解法，都是利用贪心的思路，一种是数学解法，一种会用到 priority queue 优先队列。

思路一

首先是数学的解法，思路跟358，767类似，你需要为相同字母隔开一定的距离，且首先需要保证为出现次数最多的字母隔开足够的距离。满足这个大前提之后，中间的空格就可以塞入其他字符了。这个题的思路也是类似，需要注意的细节是，如果出现次数最多的字母出现了 max 次，冷却时间为 n 的话，你需要为整个输出预留 (max - 1) * (n + 1) + 1。这个结论我第一次看的时候不理解， 后来看了一个例子记住了。

AAAABBBEEFFGG N = 3

摆放结果

任务A出现了4次，频率最高，于是我们在每个A中间加入三个空位，如下：
A---A---A---A
AB--AB--AB--A (加入B)
ABE-ABE-AB--A (加入E)
ABEFABE-ABF-A (加入F，每次尽可能填满或者是均匀填充)
ABEFABEGABFGA (加入G)

如上这个例子，max 应该是 A 出现的次数 = 4，所以预留长度应该是间隔的出现次数 * 每个间隔长度，(4 - 1) * (3 + 1) = 3 * 4 = 12。为什么呢？因为 A 出现了 4 次，其中 4 个 A 之间会需要 3 个间隔，所以次数是 3；每个间隔的长度是冷却时间 + 1，比如之前这个例子，冷却时间是 2，但是每个 A 之间的间隔是 3。

Example:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

至于具体的做法，是先用 hashmap 统计每个出现的字母及其次数，然后找出出现次数最大的字母的次数，先依据这个最大次数 max 和冷却时间 n ，算出一个符合条件的最短距离。同时注意两个 corner case

1. 如果出现次数最多的字母有多个，那么最后需要再 + 1。还是刚才这个例子

   AAAABBBEEFFGG N = 3

因为 A 出现了 4 次，所以我们为了 A，起码需要有的长度 = (max - 1) * (n + 1) + 1 = 3 * 4 + 1 = 13。这个长度只能摆放 max - 1 个 A（出现次数最多的字母）。假设如果 B 也出现了 4 次，input 字符串变成 AAAABBBBEEFFGG 的话，就要预留 12 + 2 = 14 个位置。为什么最后 + 1 变成 + 2 是需要留给第四个 B，因为最后一个 B 也没有计算在内。或者换句话说之前我们计算的长度其实是按照 gap 来算的，不是按照字母出现次数算的。

2. 会存在不需要加额外冷却时间的情形，比如 n 小于 tasks 的长度，tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 1，只要把 A 和 B 隔开排列就行了。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int max = 0;
        int[] map = new int[256];
        for (char c : tasks) {
            map[c]++;
            max = Math.max(max, map[c]);
        }

        int res = (max - 1) * (n + 1);
        for (int i = 0; i < 256; i++) {
            if (map[i] == max) {
                res++;
            }
        }
        return Math.max(res, tasks.length);
    }
}

思路二

再来是 priority queue 的做法。首先用 pq 建立一个最大堆，记录存每个字母的出现次数，出现次数最多的字母会在堆顶。再创建一个 cycle 变量，长度是 n + 1，这是每个间隔的长度。接着开始 pop 字符，每 pop 出一个字符的时候，将他加入一个临时的 list，因为有可能还会再加回 pq。每次如果在 cycle 跑完之前，pq 就遍历完了，则加入 worktime，如果 pq 没有遍历完，则加入 pq 的 size。

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现

class Solution {
    public int leastInterval(char[] tasks, int n) {
        HashMap<Character, Integer> counts = new HashMap<>();
        for (char t : tasks) {
            counts.put(t, counts.getOrDefault(t, 0) + 1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        queue.addAll(counts.values());

        int res = 0;
        int cycle = n + 1;
        while (!queue.isEmpty()) {
            int worktime = 0;
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < cycle; i++) {
                if (!queue.isEmpty()) {
                    temp.add(queue.poll());
                    worktime++;
                }
            }
            for (int count : temp) {
                if (--count > 0) {
                    queue.offer(count);
                }
            }
            res += !queue.isEmpty() ? cycle : worktime;
        }
        return res;
    }
}