LeetCode_Sorting_621. Task Scheduler 任務排程器（Java）【找規律，桶思想】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​三，AC代碼​​

​​Java​​

​​四，解題過程​​

​​第一博​​

​​第二搏​​

一，題目描述

英文描述

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.

中文描述

給你一個用字元數組 tasks 表示的 CPU 需要執行的任務清單。其中每個字母表示一種不同種類的任務。任務可以以任意順序執行，并且每個任務都可以在 1 個機關時間内執行完。在任何一個機關時間，CPU 可以完成一個任務，或者處于待命狀态。

然而，兩個 相同種類 的任務之間必須有長度為整數 n 的冷卻時間，是以至少有連續 n 個機關時間内 CPU 在執行不同的任務，或者在待命狀态。

你需要計算完成所有任務所需要的 最短時間 。

示例與說明

示例 1：

示例 2：

示例 3：

提示：

1 <= task.length <= 104

tasks[i] 是大寫英文字母

n 的取值範圍為 [0, 100]

來源：力扣（LeetCode）

連結：​​​https://leetcode-cn.com/problems/task-scheduler​​ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

以下圖檔均來自​​@popopop【【任務排程器】C++ 桶子_配圖了解】​​。和官方最優題解差不多，但是解釋的更加通俗易懂。

第一種情況：冷卻時間未被占滿

 第二種情況：冷卻時間全部占滿

三，AC代碼

Java

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] record = new int[26];             // 任務名稱為26個大寫英文字母
        for (char c : tasks) record[c - 'A']++;
        int maxTask = 0;                        // 同類型任務的最大任務個數
        int numOfMaxTask = 0;                   // 滿足任務個數最大的任務種類
        for (int i = 0; i < 26; i++) {
            if (record[i] > maxTask) {
                maxTask = record[i];
                numOfMaxTask = 1;
            } else if (record[i] == maxTask) {
                numOfMaxTask++;
            }
        }
        return Math.max(tasks.length, (maxTask - 1) * (n + 1) + numOfMaxTask);
    }
}      

四，解題過程

第一博

乍一看不就是填充空缺嗎，但是越看越不對勁，從一維的角度看任務不斷疊加，不好看出其中的規律，而且漏掉了一個重要的條件：冷卻時間至少為n，也就是說比n大也滿足條件。 

第二搏