Skip to content

Commit 34b4d6f

Browse files
committed
621.任务调度器,桶填充
1 parent 6abae41 commit 34b4d6f

File tree

3 files changed

+42
-0
lines changed

3 files changed

+42
-0
lines changed

leetcode_Java/DoneTitle.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -138,6 +138,7 @@
138138
583. 两个字符串的删除操作
139139
589. N叉树的前序遍历
140140
617. 合并二叉树
141+
621. 任务调度器
141142
647. 回文子串
142143
674. 最长连续递增序列
143144
695. 岛屿的最大面积

leetcode_Java/DoneType.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -178,6 +178,7 @@
178178
448. 找到所有数组中消失的数字(计数,集合,置换)
179179
560. 和为 K 的子数组(前缀和,哈希表)
180180
581. 最短无序连续子数组(排序,双指针)
181+
621. 任务调度器(桶填充)
181182
704. 二分查找
182183
867. 转置矩阵(置换)
183184

leetcode_Java/Solution0621.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
// 621. 任务调度器
2+
3+
4+
/*
5+
桶填充:
6+
1、统计每个任务的数量,以最大任务数为桶的数量,一行为一个桶
7+
2、冷却为n,以n+1为桶的容量,因为执行同样的任务时间间隔为n+1,冷却时间内可以执行其他任务
8+
3、任务填桶,当桶存在空闲空间时,即桶没有填满。不是最后一个桶则存在等待时间,最后一个桶则不存在等待时间,因为任务要结束了。
9+
所以“总排队时间t1 = (桶个数 - 1) * (n + 1) + 最后一桶的任务数”
10+
4、当桶不存在空闲空间时,即桶填满了,所有任务都依次不断地在单位时间内执行完成,所以“总排队时间t2 = 任务总数”
11+
5、存在空闲空间时 t1 比较大,不存在空闲空间时 t2 比较大,所以完成所有任务所需要的最短时间为 max(t1, t2)
12+
13+
A B C
14+
A B C
15+
A B
16+
A B
17+
=========
18+
A B C D
19+
A B C E
20+
A B C F
21+
A B D
22+
*/
23+
class Solution {
24+
public int leastInterval(char[] tasks, int n) {
25+
int[] count = new int[26];
26+
for (char task : tasks) {
27+
count[task - 'A']++;
28+
}
29+
int maxTask = 0, rest = 0;
30+
for (int i = 0; i < 26; i++) {
31+
if (count[i] > maxTask) {
32+
maxTask = count[i];
33+
rest = 1;
34+
} else if (count[i] == maxTask) {
35+
rest += 1;
36+
}
37+
}
38+
return Math.max(tasks.length, (maxTask - 1) * (n + 1) + rest);
39+
}
40+
}

0 commit comments

Comments
 (0)