任務(wù)調(diào)度器

• https://leetcode.cn/problems/task-scheduler/

描述

• 給你一個(gè)用字符數(shù)組 tasks 表示的 CPU 需要執(zhí)行的任務(wù)列表。其中每個(gè)字母表示一種不同種類的任務(wù)。任務(wù)可以以任意順序執(zhí)行，并且每個(gè)任務(wù)都可以在 1 個(gè)單位時(shí)間內(nèi)執(zhí)行完。在任何一個(gè)單位時(shí)間，CPU 可以完成一個(gè)任務(wù)，或者處于待命狀態(tài)。

• 然而，兩個(gè) 相同種類 的任務(wù)之間必須有長(zhǎng)度為整數(shù) n 的冷卻時(shí)間，因此至少有連續(xù) n 個(gè)單位時(shí)間內(nèi) CPU 在執(zhí)行不同的任務(wù)，或者在待命狀態(tài)。

• 你需要計(jì)算完成所有任務(wù)所需要的最短時(shí)間。

示例 1：

輸入：tasks = ["A","A","A","B","B","B"], n = 2
輸出：8
解釋：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，兩個(gè)相同類型任務(wù)之間必須間隔長(zhǎng)度為 n = 2 的冷卻時(shí)間，而執(zhí)行一個(gè)任務(wù)只需要一個(gè)單位時(shí)間，所以中間出現(xiàn)了（待命）狀態(tài)。 

示例 2：

輸入：tasks = ["A","A","A","B","B","B"], n = 0
輸出：6
解釋：在這種情況下，任何大小為 6 的排列都可以滿足要求，因?yàn)?n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
諸如此類

示例 3：

輸入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
輸出：16
解釋：一種可能的解決方案是：
     A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

提示：

• 1 <= task.length <= $10^4$
• tasks[i] 是大寫(xiě)英文字母
• n 的取值范圍為 [0, 100]

算法實(shí)現(xiàn)

1 ）方案 1

function leastInterval(tasks: string[], n: number): number {
    let result = '' // 最終隊(duì)列執(zhí)行的結(jié)果
    const dict = {} // 對(duì)歸類進(jìn)行存儲(chǔ)
    tasks.forEach((item) => {
        dict[item] ? (dict[item] ++) : (dict[item] = 1)
    })
    while(true) {
        // 任務(wù)清單
        const keys = Object.keys(dict)
        // 任務(wù)處理完畢跳出
        if (!keys.length) {
            break
        }
        // 正常處理過(guò)程
        let tmp = [] // 用于存儲(chǔ) 1 + n個(gè)任務(wù)單元
        for (let i = 0; i <= n; i++) {
            let max:number = 0 // 找到最大的任務(wù)
            let key:string
            let pos:number
            // 遍歷任務(wù)清單
            keys.forEach((item, idx) => {
                // 當(dāng)前任務(wù)數(shù)量大于max
                if (dict[item] > max) {
                    max = dict[item] // 存儲(chǔ)更新max
                    key = item // 存儲(chǔ)更新當(dāng)前任務(wù)
                    pos = idx // 存儲(chǔ)更新當(dāng)前任務(wù)下標(biāo)索引，用于后續(xù)的刪除操作
                }
            })
            // 沒(méi)有匹配到key, 直接跳出此次循環(huán)
            if (!key) {
                break
            }
            // 找到了key
            tmp.push(key) // 臨時(shí)隊(duì)列添加當(dāng)前的key
            keys.splice(pos, 1) // 將當(dāng)前key從任務(wù)隊(duì)列中刪除
            dict[key] -- // 更新key的長(zhǎng)度，已消費(fèi)完成，刪除來(lái)更新剩余個(gè)數(shù)
            // 當(dāng)全部消費(fèi)完成，移除當(dāng)前的任務(wù)
            if (dict[key] < 1) {
                delete dict[key]
            }
        }
        result += tmp.join('').padEnd(n + 1, '-') // 如果不全，補(bǔ)充冷卻時(shí)間
    }
    // 邊界的處理, 最后不要出現(xiàn)冷卻時(shí)間
    result = result.replace(/-+$/, '')
    return result.length
}

• 關(guān)鍵需求分析：
  • 兩個(gè) 相同種類 的任務(wù)之間必須有長(zhǎng)度為整數(shù) n 的冷卻時(shí)間
  • 因此至少有連續(xù) n 個(gè)單位時(shí)間內(nèi) CPU 在執(zhí)行不同的任務(wù)，或者在待命狀態(tài)。
  • 要求，完成所有任務(wù)的最短時(shí)間
• 從上面的描述和示例中可見(jiàn)
  • 隊(duì)列中有A,B,C,…, 現(xiàn)在開(kāi)啟了一個(gè)任務(wù)
  • 如果當(dāng)前開(kāi)啟了A任務(wù)，那接下來(lái)n個(gè)的任務(wù)中不能有A了
  • 如果其他任務(wù)不夠n的長(zhǎng)度，那么要冷卻等待
  • 只要現(xiàn)在隊(duì)列中還有任務(wù)，我就要處理任務(wù)本身和n個(gè)任務(wù)冷卻時(shí)間的 n+1 的任務(wù)，
  • 也就是從隊(duì)列中取出這些任務(wù)來(lái)存放，求最短的存放時(shí)間
    • 如何做到最短，考慮使用最多的任務(wù)優(yōu)先處理，盡量不會(huì)有剩余，交叉著來(lái)
    • 少的來(lái)進(jìn)行插縫作業(yè)，這樣即保證少的任務(wù)使用了
    • 又保證多的任務(wù)不會(huì)用冷卻時(shí)間處理來(lái)占用更多資源
• 這個(gè)算法，在實(shí)現(xiàn)上效率不高

2 ）方案 2文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-433660.html

function leastInterval(tasks: string[], n: number): number {
  // 初始化一個(gè)矩陣，用于存儲(chǔ)給定任務(wù)的數(shù)量的字典
  const cnts = Array(26).fill(0);
  for(const c of tasks) {
    cnts[c.charCodeAt(0) - 'A'.charCodeAt(0)]++;
  }
  // 統(tǒng)計(jì)出任務(wù)中對(duì)多的數(shù)量
  let max = 0, tot = 0;
  for (let i = 0; i < 26; i++) {
    max = Math.max(max, cnts[i]);
  }
  // 更新tot變量的值，用于統(tǒng)計(jì)具有最多執(zhí)行次數(shù)的任務(wù)數(shù)量
  for (let i = 0; i < 26; i++) {
    tot += max === cnts[i] ? 1 : 0;
  }
  // 這里是最核心的算法
  return Math.max(tasks.length, (n + 1) * (max - 1) + tot)
};

• 這是官方示例，效率很高
• 這里用到charCodeAt() 方法可返回指定位置的字符的 Unicode 編碼
• 后續(xù)有時(shí)間再研究下：https://leetcode.cn/problems/task-scheduler/solution/ren-wu-diao-du-qi-by-leetcode-solution-ur9w/ 中的方法二：構(gòu)造

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法之隊(duì)列: Leetcode 621. 任務(wù)調(diào)度器 (Typescript版)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！