LeetCode#621

LeetCode#621任务调度器

题目链接
给你一些任务，任务分别是A-Z的大写字母表示，再给你一个n，表示两个相同的任务直接必须间隔n个时间单位（比如你在1时刻执行了一个A任务，n为2，那么你在时刻2和时刻3就只能执行其他的任务或者等待，直到时刻3及以后才可以继续执行），问完成全部任务最少需要多少时间。
我一开始是觉得这东西只能拿模拟来写，毕竟一共才26个英文字母，就算遍历几遍也还是O(n)的时间复杂度（=，模拟思路就很简单了，先遍历一遍整个tasks，然后统计出每种任务分别有多少个，然后一个一个的模拟就行，直到如果没有和这个任务不同的任务了，就选择等待。
然后看了题解，好像打开了一个新世界。。。原来这题还能这么想，怪不得有脑筋急转弯的标签（逃。
假设在当前这个tasks中，A为出现次数最多的一个任务类型，接下来我们是不是可以这么理解呢:先找出出现次数最多的一个任务，这样我们只需要在每一次出现这个任务时在它的后面填充n个任务（包括等待），直到所有A都完成，那么就完成了所有任务呢（假设有a个A，tasks.size()=b，n=c，先暂时认为b-a<=(a-1)n），我们设max_elem为出现最多次数任务的出现次数，max_elem_cnt为出现次数等于max_elem的任务的个数。所以最少时间就为(max_elem-1)(n+1)+max_elem_cnt。
接下来就比较简单了，直接上代码：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int len = tasks.size();
        int ans;
           vector<int> cnt(30,0);
           for(int i = 0 ; i < len ; i++)
                cnt[tasks[i]-'A']++;
            ans = 0;
            int pos = max_element(cnt.begin(),cnt.end())-cnt.begin();
            int max_elem=cnt[pos];
            int max_elem_cnt = 0;
            for(int i = pos ; i < 26 ; i++)
                if(cnt[i] == max_elem)
                    max_elem_cnt++;
            ans = (max_elem-1)*(n+1)+max_elem_cnt;
        return max(ans,len);
    }
};