Leetcode-Medium 621. Task Scheduler

2019-03-15 10:38:22 浏览数 (1)

题目描述

给定一个char数组表示CPU需要执行的任务。它包含大写字母A到Z，其中不同的字母代表不同的任务。每项任务都可以在一个时间间隔内完成。对于每个间隔，CPU可以完成一个任务或空闲。但是有规定一个非负整数n代表两个相同任务之间需要至少n个时间单位。球最少数量的时间单位完成所有任务。

需要返回CPU将完成所有给定任务所需的最少间隔数。

实例：

代码语言：javascript复制
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

思路

dicussion 分享的思路concise Java Solution O(N) time O(26) space，通过分析人物队列的规律来计算：

首先考虑出现次数最多的字符，我们可以先确定它们的相对位置，然后将它们用作框架来插入剩余的不常用的字符

通过上面的分析，我们可以发现最少任务时间为：（最多任务数-1）*（n 1） （相同最多任务的任务个数）。

假设AAAABBBBCCDE，n=3，那么时间为：(NUM(A)-1)*(3 1) 2=14

代码实现

代码语言：javascript复制
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        c=collections.Counter(tasks)
        mc,tie_ct=c.most_common(1)[0][1],0
        for k,v in c.most_common()[1:]:
            if v==mc:
                tie_ct =1
            else:
                break
        return max(len(tasks),(mc-1)*n mc tie_ct)

参考资料

  • Task Scheduler - LeetCode [图片上传失败...(image-60182f-1551694438422)]
  • Leetcode 621. Task Scheduler（贪心） | 张慕晖的博客
  • concise Java Solution O(N) time O(26) space - LeetCode Discuss [图片上传失败...(image-899c54-1551694438422)]
  • [LeetCode]621. Task Scheduler 任务安排 题解 - Fanny123 - 博客园 [图片上传失败...(image-5eb8e8-1551694438421)]
  • LeetCode-621：Task Scheduler (任务调度) -- medium - 大树先生的博客 - CSDN博客
codeigniter

0 人点赞