LeetCode：621. Task Scheduler（任务规划问题）

桃扇骨 2022-04-03 14:58 193阅读 0赞

**文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

**文章目录：**

题目描述：

java实现方法1：

python实现方法1：

源码github地址：https://github.com/zhangyu345293721/leetcode

--------------------

### **题目描述：** ###

给定一个用字符数组表示的 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\]。

来源：力扣（LeetCode）

--------------------

假设最大任务执行次数是maxCount，该任务编号是A，我们不考虑其他任务，其需要的等待时间是(maxCount - 1) \* n。

（1）如果还有执行次数为p的最大任务，该任务编号是B，该任务中的(p - 1)个任务可以在A的等待时间内完成，如果B在A的等待时间内完成，那么那段时间就不能算进等待时间里，因此总等待时间需要减去p - 1。

（2）如果某个执行次数为q的任务，其任务编号是C，显然，所有该任务都能再原来的等待时间内完成，因此总等待时间需要减去q。

最后返回结果时，如果计算出的等待时间是负数，这是不切实际的，我们直接返回tasks数组的长度。否则，我们返回的是tasks数组的长度加上等待时间。

--------------------

### java实现方法1： ###

/**
         * 任务规划
         *
         * @param tasks 任务数组
         * @param n     规划数
         * @return 数量
         */
        public int leastInterval(char[] tasks, int n) {
            int[] map = new int[26];
            for (char c : tasks) {
                map[c - 'A']++;
            }
            Arrays.sort(map);
            int maxHeight = map[25] - 1;
            int maxSlots = maxHeight * n;
            for (int i = 24; i >= 0 && map[i] != 0; i--) {
                maxSlots -= Math.min(maxHeight, map[i]);
            }
            return Math.max(tasks.length + maxSlots, tasks.length);
        }

时间复杂度：O(n.logn)

空间复杂度：O(n)

--------------------

### python实现方法1： ###

def least_interval(tasks: List[chr], n: int) -> int:
        '''
            任务分配问题
        Args:
            tasks:任务数组
            n:数量
        Returns:
            数字
        '''
        map = [0] * 26
        for ch in tasks:
            map[ord(ch) - ord('A')] += 1
        map.sort()
        max_height = map[25] - 1
        max_slots = max_height * n
        i = 24
        while i >= 0 and map[i] != 0:
            max_slots -= min(max_height, map[i])
            i += 1
        return max(len(tasks) + max_slots, len(tasks))

时间复杂度：O(n.logn)

空间复杂度：O(n)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode