# **Leetcode筆記(Task Scheduler)**

:::info
:information_source: 題目 : Task Scheduler, 類型 : heap , 等級 : medium
日期 : 2023/06/07，2023/07/09，2024/09/13
:::

### 嘗試
2023/07/09
最佳化通式 : (maxF - 1) * (n + 1) + sameF
如果len(tasks)還大於res，代表最佳化長度還比較短，代表皆為高頻率出現字母，那必定可以互相穿插

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        record = {}
        for t in tasks:
            record[t] = 1 + record.get(t, 0)
        
        maxCount = max(record.values()) # 頻率最高出現次數
        sameCountNum = 0 # 有沒有出現相同次數的num(一定有1(自己本身))
        for num in record.values():
            if num == maxCount:
                sameCountNum += 1 

        res = (n + 1) * (maxCount - 1) + sameCountNum # 最佳化通式

        if res > len(tasks): 
            return res
        return len(tasks) # 如果最佳化長度還比較短 代表皆為高頻率出現字母 那必定可以互相穿插

2024/09/13

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        record = defaultdict(int)
        for c in tasks:
            record[c] += 1
        
        maxFreq = max(record.values())
        sameFreq = 0

        for c, count in record.items():
            if count == maxFreq:
                sameFreq += 1
        
        return max(len(tasks), (n + 1) * (maxFreq - 1) + sameFreq)

---
### **優化**
假設有[A,A,A,B,B,B,B]，n=2，會先將最大的排下去並且空好空格
B _ _ B _ _ B _ _ B
然後再將剩下的字母依序排下去
B A _ B A _ B A _ B
(B A _ )(B A _ )(B A _ )B
B出現的次數 - 1 = 除了最後一個B 其他都算
每個group(括號處)的大小為3 = B的佔位 + 兩個規定空格
最後需要補上沒有算的B
(4 - 1) * (2 + 1) + 1 = 10

假設有[A,A,A,B,B,B]，n=2，有兩個出現次數依樣多的，代表有多一個要補在最後面
B _ _ B _ _ B
B A _ B A _ B A
(B A _ )( B A _ ) B A
(3 - 1) * (2 + 1) + 2 = 8

注意 : 當 (maxF - 1) * (n + 1) + sameF 的值小於任務總數時，意味著間隔不足以執行所有的任務。在這種情況下，我們應該返回任務總數，以確保所有的任務都能被執行完畢。

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        record = {}
        for t in tasks:
            record[t] = 1 + record.get(t, 0)
        
        maxF = max(record.values())
        sameF = 0
        for val in record.values():
            if val == maxF:
                sameF += 1
        
        return max(len(tasks), (maxF - 1) * (n + 1) + sameF)

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=Z2Plc8o1ld4
Provided by. Sai Anish Malla

###### tags: `heap` `medium` `leetcode`