Task Scheduler解题报告

Description:

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example:

Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Link:

https://leetcode.com/problems/task-scheduler/description/

解题方法：

将每种任务个数统计起来，从大到小排序并且遍历。
假设出现出现最多的任务个数为k个，那么一开始我们有：(k-1)*n + k个interval。
这期中我们有(k-1)*n个空的可以填充其他任务，如果这些空隙没有被填充，则要被填充idle。
假设空隙都用完了，那么接下来的任务还是可以添加到之前空隙的位置，但是此时因为空隙已经用完，每次添加进来的任务数都要算到总数里面。
当空隙没有用完时，每次碰到有k个数量的任务时，我们肯定要在末尾添加一个该任务，所以此时总数+1。
而最难理解的部分是，这些空隙是不是都会被填充完，答案是肯定的，因为当碰上任务数较小的任务时，可能会出现前面的空隙被填充完而后面的空隙没有，但是这没有关系，因为之后不管遇到什么数量的任务，之前留下的空隙都可以拿来使用并且不会影响每个相同任务之间的间隔。

犯的错误:

每个相同任务之间是至少需要n个间隔，但是间隔可以大于n。

Time Complexity：

O(N): N为总任务数。

完整代码：

int leastInterval(vector<char>& tasks, int n) 
    {
        if(!n)
            return tasks.size();
        vector<int> hash(26, 0);
        for(char ch: tasks)
            hash[ch - 'A']++;
        sort(hash.begin(), hash.end(), [](int a, int b){
            return a > b;
        });
        int total = 0, zoom = 0, left = 0;
        total += hash[0] + (hash[0] - 1) * n;
        zoom = (hash[0] - 1) * n;
        for(int i = 1; i < hash.size(); i++)
        {
            if(hash[0] == hash[i])
            {
                total++;
                left += hash[i] - 1;
                continue;
            }
            left += hash[i];
        }
        return max(total, total + (left - zoom));
    }