题目描述：

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()))

 

本文链接：http://bookshadow.com/weblog/2017/06/18/leetcode-task-scheduler/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码