python - 构建贪心任务调度器——Python算法

Question

正在解决以下 Leetcode 问题:https://leetcode.com/problems/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.

例子:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

我编写的代码通过了大部分 Leetcode 测试用例，但在输入非常大时却失败了。这是我的代码:

import heapq
from collections import Counter

class Solution(object):
    def leastInterval(self, tasks, n):
        CLOCK = 0
        if not tasks:
            return len(tasks) 

        counts = Counter(tasks)
        unvisited_tasks = counts.most_common()[::-1]
        starting_task, _ = unvisited_tasks.pop()
        queue = [[0, starting_task]]

        while queue or unvisited_tasks:
            while queue and CLOCK >= queue[0][0]:
                _, task = heapq.heappop(queue)
                counts[task] -= 1
                if counts[task] > 0:
                    heapq.heappush(queue, [CLOCK + 1 + n, task])
                CLOCK += 1

            if unvisited_tasks:
                t, _ = unvisited_tasks.pop()
                heapq.heappush(queue, [0, t])
            else:
                # must go idle
                if queue:
                    CLOCK += 1

        return CLOCK 

这是(大)输入案例:

tasks = ["G","C","A","H","A","G","G","F","G","J","H","C","A","G","E","A","H","E","F","D","B","D","H","H","E","G","F","B","C","G","F","H","J","F","A","C","G","D","I","J","A","G","D","F","B","F","H","I","G","J","G","H","F","E","H","J","C","E","H","F","C","E","F","H","H","I","G","A","G","D","C","B","I","D","B","C","J","I","B","G","C","H","D","I","A","B","A","J","C","E","B","F","B","J","J","D","D","H","I","I","B","A","E","H","J","J","A","J","E","H","G","B","F","C","H","C","B","J","B","A","H","B","D","I","F","A","E","J","H","C","E","G","F","G","B","G","C","G","A","H","E","F","H","F","C","G","B","I","E","B","J","D","B","B","G","C","A","J","B","J","J","F","J","C","A","G","J","E","G","J","C","D","D","A","I","A","J","F","H","J","D","D","D","C","E","D","D","F","B","A","J","D","I","H","B","A","F","E","B","J","A","H","D","E","I","B","H","C","C","C","G","C","B","E","A","G","H","H","A","I","A","B","A","D","A","I","E","C","C","D","A","B","H","D","E","C","A","H","B","I","A","B","E","H","C","B","A","D","H","E","J","B","J","A","B","G","J","J","F","F","H","I","A","H","F","C","H","D","H","C","C","E","I","G","J","H","D","E","I","J","C","C","H","J","C","G","I","E","D","E","H","J","A","H","D","A","B","F","I","F","J","J","H","D","I","C","G","J","C","C","D","B","E","B","E","B","G","B","A","C","F","E","H","B","D","C","H","F","A","I","A","E","J","F","A","E","B","I","G","H","D","B","F","D","B","I","B","E","D","I","D","F","A","E","H","B","I","G","F","D","E","B","E","C","C","C","J","J","C","H","I","B","H","F","H","F","D","J","D","D","H","H","C","D","A","J","D","F","D","G","B","I","F","J","J","C","C","I","F","G","F","C","E","G","E","F","D","A","I","I","H","G","H","H","A","J","D","J","G","F","G","E","E","A","H","B","G","A","J","J","E","I","H","A","G","E","C","D","I","B","E","A","G","A","C","E","B","J","C","B","A","D","J","E","J","I","F","F","C","B","I","H","C","F","B","C","G","D","A","A","B","F","C","D","B","I","I","H","H","J","A","F","J","F","J","F","H","G","F","D","J","G","I","E","B","C","G","I","F","F","J","H","H","G","A","A","J","C","G","F","B","A","A","E","E","A","E","I","G","F","D","B","I","F","A","B","J","F","F","J","B","F","J","F","J","F","I","E","J","H","D","G","G","D","F","G","B","J","F","J","A","J","E","G","H","I","E","G","D","I","B","D","J","A","A","G","A","I","I","A","A","I","I","H","E","C","A","G","I","F","F","C","D","J","J","I","A","A","F","C","J","G","C","C","H","E","A","H","F","B","J","G","I","A","A","H","G","B","E","G","D","I","C","G","J","C","C","I","H","B","D","J","H","B","J","H","B","F","J","E","J","A","G","H","B","E","H","B","F","F","H","E","B","E","G","H","J","G","J","B","H","C","H","A","A","B","E","I","H","B","I","D","J","J","C","D","G","I","J","G","J","D","F","J","E","F","D","E","B","D","B","C","B","B","C","C","I","F","D","E","I","G","G","I","B","H","G","J","A","A","H","I","I","H","A","I","F","C","D","A","C","G","E","G","E","E","H","D","C","G","D","I","A","G","G","D","A","H","H","I","F","E","I","A","D","H","B","B","G","I","C","G","B","I","I","D","F","F","C","C","A","I","E","A","E","J","A","H","C","D","A","C","B","G","H","G","J","G","I","H","B","A","C","H","I","D","D","C","F","G","B","H","E","B","B","H","C","B","G","G","C","F","B","E","J","B","B","I","D","H","D","I","I","A","A","H","G","F","B","J","F","D","E","G","F","A","G","G","D","A","B","B","B","J","A","F","H","H","D","C","J","I","A","H","G","C","J","I","F","J","C","A","E","C","H","J","H","H","F","G","E","A","C","F","J","H","D","G","G","D","D","C","B","H","B","C","E","F","B","D","J","H","J","J","J","A","F","F","D","E","F","C","I","B","H","H","D","E","A","I","A","B","F","G","F","F","I","E","E","G","A","I","D","F","C","H","E","C","G","H","F","F","H","J","H","G","A","E","H","B","G","G","D","D","D","F","I","A","F","F","D","E","H","J","E","D","D","A","J","F","E","E","E","F","I","D","A","F","F","J","E","I","J","D","D","G","A","C","G","G","I","E","G","E","H","E","D","E","J","B","G","I","J","C","H","C","C","A","A","B","C","G","B","D","I","D","E","H","J","J","B","F","E","J","H","H","I","G","B","D"]
n = 1

我的代码输出的间隔计数为 1002，正确答案是 1000。由于输入大小太大，我无法手动调试哪里出了问题。

我的算法基本上执行以下操作:

1. 建立字符到出现次数的映射
2. 从出现次数最多的任务开始。
3. 当您访问一个任务时，将下一个任务排入队列，以便稍后进行 CLOCK + 间隔迭代，因为我的前提是您希望尽快访问任务。您可以这样做。
4. 如果不能访问一个已经访问过的任务，将一个新的任务加入队列，并且在不增加时钟的情况下这样做。
5. 如果队列中有元素，但时间不够，请增加时钟。

最后，CLOCK 变量描述了在您能够运行所有任务之前经过了多长时间(换句话说，有多少“间隔”)。

有人能发现我逻辑中的错误吗？

---

Answer 1

考虑延迟 n=1 的情况，并且您有一个这样的任务分配，其中最少的循环次数就是列表的长度(任务可以像“ABCABC...D”一样运行):

{"A": 100, "B": 100, "C": 99, "D": 1 } # { "task": <# of occurrences>, ...

使用您的算法，您将首先处理“A”和“B”的所有情况，因为您希望尽快进入同一类型的下一个任务，而不考虑其他任务类型。处理完这两个之后，您将得到:

{"C": 99, "D": 1}

这导致至少 96 个空闲周期。

要解决此问题，理想的任务配置应该类似于某种循环法。