621. 任務(wù)調(diào)度器
難度中等231 收藏 分享 切換為英文 關(guān)注 反饋
給定一個(gè)用字符數(shù)組表示的 CPU 需要執(zhí)行的任務(wù)列表。其中包含使用大寫的 A - Z 字母表示的26 種不同種類的任務(wù)唱蒸。任務(wù)可以以任意順序執(zhí)行邦鲫，并且每個(gè)任務(wù)都可以在 1 個(gè)單位時(shí)間內(nèi)執(zhí)行完。CPU 在任何一個(gè)單位時(shí)間內(nèi)都可以執(zhí)行一個(gè)任務(wù)神汹，或者在待命狀態(tài)庆捺。
然而古今，兩個(gè)相同種類的任務(wù)之間必須有長(zhǎng)度為** n **的冷卻時(shí)間，因此至少有連續(xù) n 個(gè)單位時(shí)間內(nèi) CPU 在執(zhí)行不同的任務(wù)滔以，或者在待命狀態(tài)沧卢。
你需要計(jì)算完成所有任務(wù)所需要的最短時(shí)間。
示例 ：
<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">輸入：tasks = ["A","A","A","B","B","B"], n = 2
輸出：8
解釋：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
提示：
- 任務(wù)的總個(gè)數(shù)為
[1, 10000]醉者。 -
n的取值范圍為[0, 100]但狭。
拿到題之后可以看出這是一道最優(yōu)解的問題，簡(jiǎn)單點(diǎn)的話用貪心就能解決不行的話用動(dòng)態(tài)規(guī)劃解撬即。首先貪心的思想思考下立磁，用數(shù)字最多的字母優(yōu)先按間隔排開，第二多的次之剥槐。根據(jù)測(cè)試用例似乎沒什么毛病唱歧，嘗試一下。
public int leastInterval(char[] tasks, int n) {
//若10000個(gè)數(shù)都為同一個(gè)字母粒竖，間隔為100颅崩，需要開10000 * 100 這么大的數(shù)組 稍微多給點(diǎn)
// （可以算一下內(nèi)存，但不影響實(shí)現(xiàn)初步思路
char[] array = new char[tasks.length * (n + 1)];
Map<Character, Integer> map = new HashMap<>();
// 統(tǒng)計(jì)每個(gè)字符的個(gè)數(shù)
for (char c : tasks) {
Integer k = 0;
if ((k = map.get(c)) != null) {
map.put(c, ++k);
} else {
map.put(c, 1);
}
}
// Map轉(zhuǎn)成List用來按數(shù)量排序
List<Map.Entry<Character, Integer>> list = new ArrayList<>();
Iterator iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
list.add((Map.Entry<Character, Integer>) iterator.next());
}
Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
@Override
public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
return o2.getValue() - o1.getValue();
}
});
// 接著開始給數(shù)組賦值
int ans = 0;
for (int i = 0; i < list.size(); i++) {
int k = i;
for (int j = 0; j < list.get(i).getValue(); j++) {
if (array[k] == 0) {
ans = Math.max(ans, k);
array[k] = list.get(i).getKey();
k += n + 1;
} else {
// 找到一個(gè)空的位置
while (array[++k] != 0);
ans = Math.max(ans, k);
array[k] = list.get(i).getKey();
}
}
}
// 因?yàn)閺?開始計(jì)的 所以結(jié)果+1
return ans + 1;
}
根據(jù)這個(gè)代碼的空間復(fù)雜度 100 * 10000 和 時(shí)間復(fù)雜度約 （1+ n）* n / 2 來算蕊苗，這題根本過不了沿后。提交代碼準(zhǔn)備截個(gè)圖繼續(xù)寫優(yōu)化，結(jié)果朽砰。尖滚。。
換一個(gè)思路繼續(xù)講瞧柔。漆弄。。
剛才是先按照最多的字母來插空造锅，現(xiàn)在換一種隔韭菜的方式撼唾，截取最高的，也就是數(shù)量最多的先進(jìn)入隊(duì)列哥蔚，計(jì)算量在于每次隔完一輪都需要對(duì)字母進(jìn)行重新排序倒谷。
public int leastInterval(char[] tasks, int n) {
// 統(tǒng)計(jì)字符以及數(shù)量同上。肺素。恨锚。
// i 代表第幾個(gè)入隊(duì)列,也就是最后的結(jié)果
int i = 0;
while (true) {
Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
@Override
public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
return o2.getValue() - o1.getValue();
}
});
// 因?yàn)橐獎(jiǎng)h掉用光了的字母，就用迭代器的方式
Iterator iterator1 = list.iterator();
for (int j = 0; j <= n; i++, j++) {
if (iterator1.hasNext()) {
Map.Entry<Character, Integer> entry = (Map.Entry<Character, Integer>) iterator1.next();
array[i] = entry.getKey();
int t = entry.getValue() - 1;
if (t == 0) {
iterator1.remove();
} else {
entry.setValue(t);
}
}
if (list.size() == 0) {
break;
}
}
if (list.size() == 0) {
break;
}
}
// 因?yàn)閺?開始計(jì)的 所以結(jié)果+1
return i + 1;
}
結(jié)果是比上面的更費(fèi)時(shí)倍靡，但內(nèi)存方面在上面基礎(chǔ)上還可以優(yōu)化，方法二中的array只是為了調(diào)試打印用的课舍，完全可以刪除塌西。
本文大概梳理了下自己的思考過程他挎，供大家參考與交流。
