【5分钟力扣】621.任务调度器 python

文章目录

一、题目

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

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

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

示例 1：

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

示例 2：

输入：tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
[“A”,“A”,“A”,“B”,“B”,“B”]
[“A”,“B”,“A”,“B”,“A”,“B”]
[“B”,“B”,“B”,“A”,“A”,“A”]
…
诸如此类

示例 3：

输入：tasks = [“A”,“A”,“A”,“A”,“A”,“A”,“B”,“C”,“D”,“E”,“F”,“G”], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

提示：

1 <= task.length <= 104
tasks[i] 是大写英文字母
n 的取值范围为 [0, 100]

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

二、解题思路

本题的核心是读懂题意，解题的核心思路是先安排最多次数的任务。

看例子：

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

思路分析：

执行相同任务中间必须待命单位时间（n）,题目中出现次数最多的是任务A , 所以我就先安排任务A, 然后根据任务A的空隙时间安排其他任务.

# 先那排任务A, 题目中单位时间n = 2
A -> (单位时间:1) -> (单位时间:1) -> A -> (单位时间:1) -> (单位时间:1) -> A  

中间间隔的单位时间可以用来安排别的任务，也可以处于“待命”状态。当然，为了使总任务时间最短，我们要尽可能地把单位时间分配给其他任务。现在把任务 B 安排上：

#  在待命时间间隙中安排任务B,得到如下效果:
A -> B -> (单位时间:1) -> A -> B -> (单位时间:1) -> A  -> B 

很容易观察到，前面两个 A 任务一定会固定跟着 2 个单位时间的间隔。可以将 （AB＋待命时间）看成一个整体，一共有**（A－１）**个整体

最后一个 A 之后是否还有任务跟随取决于是否存在与任务 A 出现次数相同的任务,本题A和B出现次数相同，那么很容易得到如下结论。

(任务 A 出现的次数 - 1) * (n + 1) + (最多次数的任务的个数)，即：
(3 - 1) * (2 + 1) + 2 = 8

思路总结：

1. 找到所有任务出现的次数
2. 按照任务出现次数进行排序,找出出现次数最多的任务 K
3. 计算 sum_time = 时间块 (K-1) X (n+1) + K的个数(是否存在相同次数的任务)
4. 比较最小时间和sum_time时间大小

三、代码实例

from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        k = len(tasks)
        # 考虑边界问题，如果tasks长度为1，则直接返回tasks的长度
        if k <= 1:
            return k

        # 获取各任务出现的次数
        tasks_dict = {}
        for i in tasks:
            if i in tasks_dict:
                tasks_dict[i] = tasks_dict[i] + 1
            else:
                tasks_dict[i] = 1

        # 按照出现任务次数进行降序排序，返回任务次数列表
        ls = sorted(tasks_dict.values(), reverse=True)

        # sum(ls)为理想状态下最小单位时间，即不存在待命时间
        # ls.count(ls[0]) 为出现（最多任务次数）的个数
        return max(sum(ls), (ls[0]-1)*(n+1)+ls.count(ls[0]))

if __name__ == '__main__':
    obj = Solution()
    tasks = ["A", "A", "A", "A", "C", "D", "D", "D", "C", "B", "C", "B", "D"]
    obj.leastInterval(tasks, n=2)

简化版本：

class Solution:
	def leastInterval(self, tasks: List[str], n: int) -> int:
        # 1、找出所有字母 出现次数，并按出现次数降序排列
        ls = sorted(collections.Counter(tasks).values(), reverse = True)

        # 2、找出最大次数, 有几个字母同时出现最大次数
        # 3、返回结果
        return max( sum(ls), (ls[0] - 1) * (n + 1) + ls.count(ls[0]) )