Leetcode 621. Task Scheduler (cpp)

题目

max heap解法

总体原则在于每次优先安排剩余数量最多的task，利用max heap来保持这种关系。每次从最大堆中依次取出n+1个task，然后更新task数量之后再更新max heap。这样可以保证每个task之间的冷却时间不会冲突

class Solution {
    
public:int leastInterval(vector<char>& tasks, int n) {
    unordered_map<char,int> count;for(auto c : tasks){
    count[c]++;}priority_queue<int> pq;for(auto it : count){
    pq.push(it.second);}int ans = 0;while(!pq.empty()){
    int time = 0;int cycle = n+1;vector<int> tmp;for(int i=0;i<cycle;i++){
    if(!pq.empty()){
    tmp.push_back(pq.top());pq.pop();time += 1;}}for(auto it : tmp){
    if(it - 1 > 0){
    it -= 1;pq.push(it);}}if(!pq.empty()){
    ans += cycle;}else{
    ans += time;}}return ans;}
};

数学解法

这题关键在于计算所需要添加的idle time，而这个idle time由出现最多次的task决定。不过证明就有点麻烦了，可以看这边：https://leetcode.com/problems/task-scheduler/discuss/824421/A-math-proof

class Solution {
    
public:int leastInterval(vector<char>& tasks, int n) {
    vector<int> freq(26,0);for(char task : tasks){
    freq[task - 'A'] += 1;}sort(freq.rbegin(),freq.rend());int idle_time = (freq[0] - 1) * n;int i = 1;while(i < 26 && idle_time > 0){
    idle_time -= min(freq[0] - 1, freq[i]);i++;}idle_time = max(0,idle_time);return tasks.size() + idle_time;}
};