621. Task Scheduler

O(t) time t是tasks的个数题解
先统计字符频数，然后从大到小排序，初始idle的个数是(最大频数 - 1) * n，因为只统计(最大频数 - 1)范围内的区间，比如输入是AAABBB2，则初始化为A__A__，而不是A__A__A__，然后要做的就是按照频数从大到小往idle的slot里面放字符，这里要放在区间范围内，所以要用min(m[i], mx)，即AB_AB_，否则变成AB_AB_B就不对了，所有频数大于0的字符都放完以后，如果还有idle的slot说明剩下的字符只能放在后面了，即AB_AB_AB，不能再往idle的slot里面放了，否则说明不需要idle的slot分隔也足以让字符按照要求间隔的放，比如输入AAABBBCCC2，输出应为ABCABCABC
假设task是AAABBCCDD，n = 2

1
2
3

A12
A12
A

变成

1
2
3

ABCD
ABCD
A

则所有idel slot都占满，结果就是task.size() = 9
假设task是AAABBB，n = 2

1
2
3

A12
A12
A

变成

1
2
3

AB2
AB2
AB

还剩2个idle slot，结果就是taks.size() + 2 = 8

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int m[26] = {0};
        for (char c : tasks) {
            ++m[c - 'A'];
        }
        sort(m, m + 26, greater<int>());
        int mx = m[0] - 1, idle_slots = mx * n;
        for (int i = 1; i < 26 && m[i] > 0 && idle_slots >= 0; ++i) {
            idle_slots -= min(m[i], mx); // idle_slots是有可能放不开的，也就是最后变成负数
        }
        return tasks.size() + max(idle_slots, 0); // 这里要取max是因为idle_slots有可能因为放不开而『过饱和』，也就是变成负数，最后要把这些『负数』加回来，比如AAABBBCCCDDD2，最后idle_slots因为D放不进去变成-2
    }
};