動機

以為要算所有組合數…

Problem

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

 

Example 1:

Input: tasks = [A,A,A,B,B,B], n = 2Output: 8Explanation: A -> B -> idle -> A -> B -> idle -> A -> BThere is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = [A,A,A,B,B,B], n = 0Output: 6Explanation: On this case any permutation of size 6 would work since n = 0.[A,A,A,B,B,B][A,B,A,B,A,B][B,B,B,A,A,A]...And so on.

Example 3:

Input: tasks = [A,A,A,A,A,A,B,C,D,E,F,G], n = 2Output: 16Explanation: One possible solution isA -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

 

Constraints:

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

Sol: queue

就是直接塞到queue，queue的大小就是n，一直從最多任務的開始挑

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        q = deque()
        inQ = set()
        count = {}
        times = len(tasks)
        ret = 0
        for (k,v) in dict(Counter(tasks)).items():
            if v in count:
                count[v].add(k)
            else:
                count[v] = set([k])
        while count:
            #print(count)
            nextTask = None
            index = None
            for k in sorted(count.keys(),reverse=True):
                for key in count[k]:
                    if key not in inQ:
                        nextTask = key
                        break
                if nextTask:
                    index = k
                    break
            if nextTask:
                count[index].remove(nextTask)
                if not count[index]:
                    del count[index]
                if index-1 > 0:
                    if index-1 not in count:
                        count[index-1] = set()
                    count[index-1].add(nextTask)
                q.append(nextTask)
                inQ.add(nextTask)
            else:
                q.append('idle')
            if len(q) > n:
                task = q.popleft()
                if task != 'idle':
                    inQ.remove(task)
            #print(q,heap)
            ret += 1
        return ret

Sol

先統計task的個數，找task最多出現幾次(mx)，這樣就會分出總共有幾組，因為最多的task一定會留到最後一組卻塞不滿，這樣就會有mx-1組

mx = 3
A__ A__ A

接著算一組可以塞多少個，每一組都有一個最多的task，所以剩下的n個空格，不管有沒有都要留，因此每一組可以塞n+1個

mx = 3
n = 2
A _ _ A _ _ A

最後就是塞不滿的總數有多少，就是看最多的task有幾種

mx = 3
n = 2
rest = 1
A _ _ A _ _ A
=>
(mx-1) * (n+1) + rest

但要注意，如果任務總數比算出來的數字少，最少就是要任務總數的時間

但我們只是要求時間長度，所以我們假設最多的task加上多的格子(要等的時間，所以我們可以塞別的task)可以塞完其他task，如果塞不完?

就一定要整條跑完，因為n沒得塞

最後就是

(n+1): 要等的時間+最多的task一個 (mx-1): 最多的task的task數量減一，成為(n+1)的個數 rest: 最多的task的總數，最後一定會剩下最多的task等著去做

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # 假設最後剩下來的task是最多的task，如果其他task多到漫出來，就是全跑
        ts = Counter(tasks)
        mx = ts.most_common(1)[0][1] # task數
        rest = Counter(ts.values())[mx] # 最多task的task的數量
        return max(len(tasks), (n+1)*(mx-1)+rest)