File tree Expand file tree Collapse file tree 3 files changed +42
-0
lines changed Expand file tree Collapse file tree 3 files changed +42
-0
lines changed Original file line number Diff line number Diff line change 138
138
583. 两个字符串的删除操作
139
139
589. N叉树的前序遍历
140
140
617. 合并二叉树
141
+ 621. 任务调度器
141
142
647. 回文子串
142
143
674. 最长连续递增序列
143
144
695. 岛屿的最大面积
Original file line number Diff line number Diff line change 178
178
448. 找到所有数组中消失的数字(计数,集合,置换)
179
179
560. 和为 K 的子数组(前缀和,哈希表)
180
180
581. 最短无序连续子数组(排序,双指针)
181
+ 621. 任务调度器(桶填充)
181
182
704. 二分查找
182
183
867. 转置矩阵(置换)
183
184
Original file line number Diff line number Diff line change
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
+ }
You can’t perform that action at this time.
0 commit comments