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

文章目录

一、题目

【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-1)**个整体

最后一个 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]) )
上一篇:C# 多线程处理List数据


下一篇:Windows下利用VSCode调试C/C++代码