Lintcode 945 任务计划
程序员文章站
2022-03-08 15:58:59
...
945. 任务计划
中文English
给定一个字符串,表示CPU需要执行的任务。 这个字符串由大写字母A到Z构成,不同的字母代表不同的任务。完成任务不需要按照给定的顺序。 每项任务都可以在一个单位时间内被完成。 在每个单位时间,CPU可以选择完成一个任务或是不工作。
但是,题目会给定一个非负的冷却时间“n”,表示在执行两个“相同的任务”之间,必须至少有n个单位时间,此时CPU不能执行该任务,只能执行其他任务或者不工作。
您需要返回CPU完成所有给定任务所需的最少单位时间数。
样例
样例1
输入: tasks = ['A','A','A','B','B','B'], n = 2
输出: 8
解释:
A -> B -> idle -> A -> B -> idle -> A -> B.
样例2
输入: tasks = ['A','A','A','B','B','B'], n = 1
输出: 6
解释:
A -> B -> A -> B -> A -> B.
注意事项
- 任务数量的范围为
[1, 10000]
. - 整数 n 的范围为
[0, 100]
.
-
public class Solution { /** * @param tasks: the given char array representing tasks CPU need to do * @param n: the non-negative cooling interval * @return: the least number of intervals the CPU will take to finish all the given tasks */ public int leastInterval(char[] tasks, int n) { // write your code here int[] ch = new int[26]; for(char c : tasks){ ch[c-'A']++; } Arrays.sort(ch); int i = 25; while (i>=0 && ch[i]==ch[25]){ i--; } return Math.max(tasks.length, (ch[25] - 1) * (n + 1) + 25 - i); } }