621. 任务调度器【力扣】

题意理解

给定一组任务，要求相同任务间隔n个单位时间，问执行完这些任务需要的最短时间

问题分析

贪心法

hash表

保证频率最大的任务满足条件，再将其他任务插入间隔中。

其他

链接

int leastInterval(vector<char>& tasks, int n) {
        map<char, int> dict;    //存放每个任务的频率
        int maxSize = 0, cnt = 0;
        for (auto task : tasks) {    
            dict[task]++;    //统计频率
            maxSize = max (maxSize, dict[task]);    //记录最大的频率
        }
        cnt = (maxSize - 1) * (n + 1);    //保证最大频率的任务能够分开
        for (auto p : dict) {
            if (p.second == maxSize) {    //对于不同任务相同的最大频率，单独增加这几个任务
                cnt ++;
            }
        }
        return max (cnt, (int)tasks.size());    //频率过低，按任务数即可；频率高，按频率计算结果
    }