2020/12/5 9:38:03 文章标签:

【LeetCode】621. Task Scheduler 任务调度器&#xff08;Medium&#xff09;&#xff08;JAVA&#xff09; 题目地址: https://leetcode.com/problems/diameter-of-binary-tree/ 题目描述&#xff1a; Given a characters array tasks, representing the tasks a CPU needs…

## 题目描述：

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

``````Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.
``````

Example 2:

``````Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.
``````

Example 3:

``````Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation:
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A
``````

Constraints:

• 1 <= task.length <= 104
• tasks[i] is upper-case English letter.
• The integer n is in the range [0, 100]

## 题目大意

• 1 <= task.length <= 104
• n 的取值范围为 [0, 100]

## 解题方法

``````AAAAABBBBCCDDEFG
n = 3

1. ABCDEFG
2 .ABCD
3. AB
4. AB
5. A

// 调整后
1. ABCD
2. ABCD
3. ABEF
4. ABG
5. A
``````
1. 因为 task[i] 只包含大写英文字母，就可以用一个长度 26 的一位数组来表示每个字母的出现次数
2. 遍历一次计数的数组，先把所有不同的字母取一遍，不断循环，直到没有字母剩下位置，然后组成不同的队列，就像上面实例一样，有 5 个队列
3. 可以看到队列的性质，总是字母多的在上一排，而且下一排有的字母上一排肯定有，上一排有的下一排不一定有
4. 根据队列的性质，我们可以把上一排多余的字母分给不够的一排，然后再计算对于冷却是否满足
5. 所以可以把每一列多退少补的特性，计算要补上的个数： res += n + 1 - curCount; note: 退的个数可能是多余要补的个数的，所以 res >= 0
6. note: 这里举得例子是字母顺序越靠前个数越多，实际上跟这没关系，我们也可以取出后进行排序，把个数多的排在前面，个数少的排在后面，这样和例子结果就一样了
7. note: 最后一个就不需要管了，因为最后一个的后面已经不需要冷却了
``````class Solution {
public int leastInterval(char[] tasks, int n) {
int[] chCount = new int;
for (int i = 0; i < tasks.length; i++) {
}
int count = 0;
int res = 0;
int curCount = 0;
for (int i = 0; i < chCount.length; i++) {
if (chCount[i] <= 0) continue;
curCount++;
count++;
chCount[i]--;
}
if (count < tasks.length) res += n + 1 - curCount;
}
res = Math.max(0, res);
}
}
`````` 暂无相关的数据...