方法一：貪心算法

解題思路：

使用貪心的思想，先把出現(xiàn)最多的任務(wù)分配了(即每隔n個單位時間分配一個任務(wù))，然后再把其它任務(wù)填上。如下圖

所以需要先計算各任務(wù)出現(xiàn)的次數(shù)，找到出現(xiàn)最多的任務(wù)，程序中使用map來計數(shù)，然后復(fù)制到vector，再通過自定義的比較函數(shù)cmp，對vector進行排序。

結(jié)果的計算公式為：(x - 1) * (n + 1) + num

其中，x表示出現(xiàn)次數(shù)最多的任務(wù)的次數(shù)，n表示輸入?yún)?shù)中的時間間隔，num表示出現(xiàn)次數(shù)為 x 的任務(wù)總數(shù)。

有一種特殊情況需要考慮，那就是：num的值要大于 n?的時候，例子如下：

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

按照公式(x - 1) * (n + 1) + num，結(jié)果為 2 * 3?+ 4 = 10，比tasks的size 12 還小，顯然不對。這種時候，就應(yīng)該返回tasks的size大小。

?

class Solution { public://自定義比較函數(shù)，必須在前面加上 static，不然會報錯static bool cmp(const pair<char, int> &v1, const pair<char, int> &v2){return v1.second > v2.second;}int leastInterval(vector<char>& tasks, int n) {map<char, int> mp;//先將tasks中任務(wù)計數(shù)在map中for(int i = 0; i < tasks.size(); i++){map<char, int>::iterator it;it = mp.find(tasks[i]);if(it == mp.end()) mp[tasks[i]] = 1;else mp[tasks[i]]++;}//將map中的元素轉(zhuǎn)到vector中，之后再進行sort排序，找到出現(xiàn)次數(shù)最多的任務(wù)vector<pair<char, int> > count;for(map<char, int>::iterator iter = mp.begin(); iter != mp.end(); iter++){count.push_back(make_pair(iter->first, iter->second));}sort(count.begin(), count.end(), cmp);int num = 0; //用于記錄出現(xiàn)次數(shù)最多的任務(wù)有多少個for(int i = 0; i < count.size(); i++){if(count[i].second == count[0].second) num++;else break;}//出現(xiàn)次數(shù)最多的任務(wù)為count[0].first, 其出現(xiàn)次數(shù)是count[0].secondint res = (count[0].second - 1) * (n + 1) + num;if(res < tasks.size()) return tasks.size();else return res;}};

?

其實，更簡單的方法可以直接就不需要map，只用一個包含26個元素（對應(yīng)26個字母）的vector計數(shù)，就能解答這道題目。

?

總結(jié)

以上是生活随笔為你收集整理的Leetcode 621. 任务调度器 解题思路及C++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。