LeetCode 任务调度器-Python3<八>

  • Z时代
  • 2024-01-10
  • 分类：综合

python

题目：https://leetcode-cn.com/problems/task-scheduler/description/

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

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

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

示例：

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

注：

  1. 任务的总个数为 [1, 10000]。   （这个边界点1？？不就是1个单位时间。）

  2. n 的取值范围为 [0, 100]。            （这个边界点0？？？要谨慎了 0不就是直接执行一个又一个，长度也就是队列长度。）

 

还真不会做，看了网上的各种答案，才领悟了。

思路：先排重复最多的，例如这题A - - A -- A --  （- 为间隔时间，间隔多少取决于n）,然后其他元素依次插空 ，A B - A B - A B    。除去最后的A B 模块 , 前面的模块总执行时间  （m-1）*(n+1) ， m为重复出现最多的次数 。最后模块肯定有A自己一个，至于A后面填充什么，就看哪些元素种类个数和A一样多 。最后不可能有待定了。

class Solution:
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        length = len(tasks)
        if length==1:
            return 1
        output = [0]*26
        for i in tasks:
            output[ord(i)-ord(\'A\')] = output[ord(i)-ord(\'A\')]+1
        count = 0
        len_o = 0
        max_o = max(output)
        for i in output:
            if i==max_o:
                count = count+1
        return max(length,(max_o-1)*(n+1)+count)

 

以上是 LeetCode 任务调度器-Python3<八> 的全部内容， 来源链接： utcz.com/z/388323.html

回到顶部