解题思路主要来自花花酱的这张图,首先计算出现频率最高的任务(字符),由于相同的任务间隔需要n个时间片,因此每个分组n+1,k-1个分组,最后加上频率都是最大值的任务。

这种算法存在一种特例就是频率最大的任务,无需插入idle即可无缝完成所有任务。

AC code:

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int max_cnt = INT_MIN;
        unordered_map<char,int> map;
        for(auto c:tasks)
        {
            map[c]++;
            max_cnt = max(max_cnt,map[c]);
        }
        
        int ans = (max_cnt - 1)*(n + 1);
        
        for(auto m:map)
        {
            if(m.second == max_cnt) ans++;
        }
        
        return max(ans,(int)tasks.size());
    }
};

运行效率:

Runtime: 64 ms, faster than 79.05% of C++ online submissions for Task Scheduler.
Memory Usage: 34.5 MB, less than 56.12% of C++ online submissions for Task Scheduler.