基本信息

  • 题号：621
  • 题厂：谷歌
  • 难度系数：中


有一个数组，元素代表一种任务，相同字符代表相同任务。整数 n 代表相同任务之间需要间隔的时间。所有任务执行时间都是 1……

问：执行任务，最少需要花费的时间……

例如：tasks = ["A","A","A","B","B","B"], n = 2
为了花最少时间完成任务，可以安排的顺序为：A -> B -> idle -> A -> B -> idle -> A -> B，花费时间为 8

A 任务之间间隔 2 次，B 任务之间间隔 2 次，再安排两次轮空……


解题思路

  • 初看此题，貌似没有想法。为解题，需要引入比较复杂的数据结构——heap 和 deque……😵
  • heap 把任务数组按照优先级排序，解决了让频率高的任务优先轮回的问题，以此实现花最少时间完成所有任务
  • deque 则帮助计算时间……
  • 另外还需要 hashmap 计算频率（即 heap 的优先级）……
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # count character to a hashmap
        count = Counter(tasks)
        
        # 此 heap 为 max heap，所以需要把元素绝对值负化
        maxHeap = [-cnt for cnt in count.values()]
        heapq.heapify(maxHeap)

        time = 0
        # pairs of [-cnt, idleTime]
        q = deque()
        
        # 当 heap 或 q 不为空时，说明还有任务没完成，循环需要继续
        # 按照 heap 优先级取出任务，每取出一次，剩余任务 counter -1
        # 同时把为完成任务放进 deque 冷却，当时间匹配时，说明执行相同任务之间保证了最小间隔，可以把任务放回 heap……
        while maxHeap or q:
            time += 1
            if maxHeap:
                cnt = 1 + heapq.heappop(maxHeap)
                if cnt:
                    q.append([cnt, time + n])
                    
            if q and q[0][1] == time:
                heapq.heappush(maxHeap, q.popleft()[0])
        
        return time


Constraints

  • 1 <= task.length <= 104
  • tasks[i] is upper-case English letter.
  • The integer n is in the range [0, 100].


Big O

  • Time：O（n）
  • Space：O（n）


测试

  • 不同任务混合出现
  • 时间为 0 的特殊情况
  • ……


总结

  • 重点考察对 heap 的认知……不知道什么是 heap 的小白是不可能做出来的
  • 本题应作为 heap 主要题定期复习
  • 在思路上绕来绕去，其实挺难的😭