[LeetCode]Task Scheduler

内容简介：[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()))

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

查看所有标签

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