621. Task Scheduler

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int maxFreqNum = 0;
        int maxVal = 0;
        int taskCount[26]{ 0 };
        for(auto& task : tasks)
        {
            ++taskCount[task - 'A'];
            if(maxVal == taskCount[task - 'A'])
                ++maxFreqNum;
            if(taskCount[task - 'A'] > maxVal)
            {
                maxFreqNum = 1;
                maxVal = taskCount[task - 'A'];
            }
        }
        int leftSpace = (maxVal - 1) * (n - maxFreqNum + 1);
        int leftTasks = tasks.size() - maxFreqNum * maxVal;
        int idle = max(0, leftSpace - leftTasks);
        return idle + tasks.size();
    }
};

首先对于AAABBCC的情况，先获得出现最多的任务

然后假设n=2

A??A??A

先放A，然后把中间空余的用其他的来填满，因为其他的如果有多个，那么只需要依次填入到每个间隔中去就可以了，例如

AB?AB?A

依旧可以保证他们的间隔符合要求。

如果有多个出现最多次数的任务，比如AAABBBC，n=2那就

1	A??A??A->AB?AB?AB

把AB视为一个整体X

X?X?X

此时就转化为一个XXXC,n=1的问题

由此我们可以先计算出出现最多的任务的出现次数maxVal，和出现最多的任务同时有几个maxFreqNum。

可以计算得到把这些任务放置后，空余的空间就是

leftSpace = (maxVal - 1) * (n - maxFreqNum + 1)

剩余的任务就是leftTasks = tasks.size() - maxFreqNum * maxVal

然后把其他的元素排放进空余的空间中去，如果空余的空间足够。那么需要填充idle空间就是

leftSpace - leftTasks，如果空余的空间不够了,那么上面算式结果是负，那么idle的空间是0，然后将剩余的任务填充进入之前每个分块的末尾即可。所以使用

1	max(0, leftSpace - leftTasks)

例如

AAABBBCC,n=1。放完最高频率后是

ABABAB

那么下一步只需要

ABCABCAB

如果maxFreqNum > n

例如AAABBBCCCDD,n = 1

只需要这样排

1	ABCABCABC->ABCDABCDABC

因为maxFreqNum > n可以保证符合要求

排列后由于n - maxFreqNum + 1是负数，所以剩余空间是负数，最终idle还是0，所以结果不变。

所有情况下的结果都是任务数和需要填充的idle数