[LeetCode]Task Scheduler

栏目: 编程工具 · 发布时间: 7年前

内容简介:[LeetCode]Task Scheduler

题目描述:

LeetCode 621. Task Scheduler

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ['A','A','A','B','B','B'], n = 2

Output: 8

Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

The number of tasks is in the range [1, 10000].

题目大意:

CPU执行任务调度,任务用字符数组tasks给出,每两个相同任务之间必须执行n个不同的其他任务或者空闲。

求最优调度策略下的CPU运行周期数。

解题思路:

计数 时间复杂度O(n) n为tasks的长度

对tasks按照任务进行计数,记数目最多的任务为t,其个数为tmax

问题转化为在tmax个任务之间的“槽”内尽可能安插别的任务,使idle最小化

例如输入tasks = ['A' * 5, 'B' * 5, 'C' * 4, 'D' * 2, 'E' * 1], n = 5

本例中,数目最多的任务t为'A',其个数tmax = 5

A o o o o o A o o o o o A o o o o o A o o o o o A x x x x x

标记为‘o’的部分需要填充任务或者idle,‘o’安排完毕后,剩余任务放置在标记为‘x’的部分

调度结果如下,答案为26:

A B C D E i A B C D i i A B C i i i A B C i i i A B

Python代码:

class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        cnt = collections.Counter(tasks)
        tmax = max(cnt.values())
        slots = (tmax - 1) * n
        tsum = len(tasks)
        return tsum + max(0, slots + tmax - 1 - sum(n - (n == tmax) for n in cnt.values()))

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

颠覆医疗

颠覆医疗

[美]埃里克·托普 / 张南、魏薇、何雨师 / 译言·东西文库/电子工业出版社 / 2014-1-20 / 55.00

“创造性破坏”是奥地利经济学家约瑟夫·熊彼特最著名的理论,当一个产业在革新之时,都需要大规模地淘汰旧的技术与生产体系,并建立起新的生产体系。电器之于火器、汽车之于马车、个人计算机之于照排系统,都是一次又一次的“创造性破坏”,旧的体系完全不复存在,新的体系随之取代。 “创造性破坏”已经深深地改变了我们的生活,在这个数字时代,我们身边的一切都被“数字化”了。只有一处,也许是由于其本身的根深蒂固,......一起来看看 《颠覆医疗》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具