golang中怎么利用leetcode 實現(xiàn)一個任務調(diào)度器

golang中怎么利用leetcode 實現(xiàn)一個任務調(diào)度器，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

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

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

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

示例 1：

輸入：tasks = ["A","A","A","B","B","B"], n = 2

輸出：8

解釋：A -> B -> (待命) -> A -> B -> (待命) -> A -> B

     在本示例中，兩個相同類型任務之間必須間隔長度為 n = 2 的冷卻時間，而執(zhí)行一個任務只需要一個單位時間，所以中間出現(xiàn)了（待命）狀態(tài)。 

示例 2：

輸入：tasks = ["A","A","A","B","B","B"], n = 0

輸出：6

解釋：在這種情況下，任何大小為 6 的排列都可以滿足要求，因為 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 <= 104

tasks[i] 是大寫英文字母

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

解題思路：

1，如果連續(xù)n+1個位置沒有重復的任務，就不需要待命，所以需不需要待命，由次數(shù)最多的任務決定。

2，我們假設，次數(shù)最多的任務的次數(shù)為maxCnt，可以建模一個二維表格，寬度為n+1，高度為maxCnt

3，分兩種情況：

A，不同的任務可以將（maxCnt-1）*（n+1）的位置填滿，這個時候，沒有空的位置，也就是沒有任務需要待命

B，不同的任務，不能將（maxCnt-1）*（n+1）的位置填滿，這個時候，空的位置，就是待命狀態(tài)。

4，針對情況A，說明不需要待命，所以需要時間就是任務數(shù)

5，針對情況B，不考慮maxCnt-1行，第maxCnt行的任務數(shù)，就是次數(shù)為maxCnt的任務數(shù)量maxCntNum。所以總的次數(shù)為（maxCnt-1）*（n+1）+maxCntNum

倒數(shù)第二行開始，按照反向列優(yōu)先的順序（即先放入靠左側的列，同一列中先放入下方的行），依次放入每一種任務，并且同一種任務需要連續(xù)地填入。對于任意一種任務而言，一定不會被放入同一行兩次（否則說明該任務的執(zhí)行次數(shù)大于等于maxCnt），并且由于我們是按照列優(yōu)先的順序放入這些任務，因此任意兩個相鄰的任務之間要么間隔 n（例如上圖中位于同一列的相同任務），要么間隔 n+1

6，結果是兩者中較大者

代碼實現(xiàn)

func leastInterval(tasks []byte, n int) int {   m:=make(map[byte]int)   for _,t:=range tasks{       m[t]++   }   maxCnt,maxCntNum:=0,0   for _,c:=range m{       if c>maxCnt{           maxCnt=c           maxCntNum=1       }else if c==maxCnt{           maxCntNum++       }   }   if num:=(maxCnt-1)*(n+1)+maxCntNum;num>len(tasks){       return num   }   return  len(tasks)}

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業(yè)資訊頻道，感謝您對億速云的支持。