621. 任务调度器
难度中等231 收藏 分享 切换为英文 关注 反馈
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
然而，两个相同种类的任务之间必须有长度为** n **的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 ：
<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.
提示：
- 任务的总个数为
[1, 10000]。 -
n的取值范围为[0, 100]。
拿到题之后可以看出这是一道最优解的问题，简单点的话用贪心就能解决不行的话用动态规划解。首先贪心的思想思考下，用数字最多的字母优先按间隔排开，第二多的次之。根据测试用例似乎没什么毛病，尝试一下。
public int leastInterval(char[] tasks, int n) {
//若10000个数都为同一个字母，间隔为100，需要开10000 * 100 这么大的数组 稍微多给点
// （可以算一下内存，但不影响实现初步思路
char[] array = new char[tasks.length * (n + 1)];
Map<Character, Integer> map = new HashMap<>();
// 统计每个字符的个数
for (char c : tasks) {
Integer k = 0;
if ((k = map.get(c)) != null) {
map.put(c, ++k);
} else {
map.put(c, 1);
}
}
// Map转成List用来按数量排序
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();
}
});
// 接着开始给数组赋值
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 {
// 找到一个空的位置
while (array[++k] != 0);
ans = Math.max(ans, k);
array[k] = list.get(i).getKey();
}
}
}
// 因为从0开始计的 所以结果+1
return ans + 1;
}
根据这个代码的空间复杂度 100 * 10000 和 时间复杂度约 （1+ n）* n / 2 来算，这题根本过不了。提交代码准备截个图继续写优化，结果。。。
换一个思路继续讲。。。
刚才是先按照最多的字母来插空，现在换一种隔韭菜的方式，截取最高的，也就是数量最多的先进入队列，计算量在于每次隔完一轮都需要对字母进行重新排序。
public int leastInterval(char[] tasks, int n) {
// 统计字符以及数量同上。。。
// i 代表第几个入队列,也就是最后的结果
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();
}
});
// 因为要删掉用光了的字母，就用迭代器的方式
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;
}
}
// 因为从0开始计的 所以结果+1
return i + 1;
}
结果是比上面的更费时，但内存方面在上面基础上还可以优化，方法二中的array只是为了调试打印用的，完全可以删除。
本文大概梳理了下自己的思考过程，供大家参考与交流。
