---
# System prepended metadata

title: 0621. Task Scheduler
tags: [Leetcode, FaceBook, Task Schedule, Medium, Greedy]

---

# 0621. Task Scheduler
###### tags: `Leetcode` `Medium` `FaceBook` `Greedy` `Task Schedule`
Link: https://leetcode.com/problems/task-scheduler/

## 思路 贪心算法 O(N) O(1)
注意区分标有task schedule的三题
先找出出现频率最高的字母出现的频率，然后把他们互相间隔为n排好
![](https://i.imgur.com/WALQ3ZW.png)
这时得到最大的idle time，然后再看其他的字母，把他们塞进idle time里面
- 如果B跟A出现的频率一样，那么就塞freq[A]-1个B进去，多出来的B排在最后一个A后面（这个B不会影响idleTime）
- 如果B出现的频率比A小，那么就塞freq[B]个B进去

也就是```idleTime-=Math.min(freq[i],freq[25-1]);```

如果最后发现idleTime<0，说明之前A的间隔不够大，只要扩展到够大就可以了，也不会影响idleTime，所以```idleTime=Math.max(0,idleTime)```

最后的结果就是idleTime+tasks.length
## Code
```java=
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        for(char c:tasks){
            freq[c-'A']++;
        }
        Arrays.sort(freq);
        int idleTime = (freq[25]-1)*n;
        for(int i = 24;i>=0 && idleTime>=0;i--){
            idleTime -= Math.min(freq[i],freq[25]-1);
        }
        return Math.max(0,idleTime)+tasks.length;
    }
}
```