621. Task Scheduler

问题：

给定任务数组，每个任务用一个大写字母表示。

给定相同任务之间的缓冲间隔 n（间隔中可填充其他任务，若没有则使之空闲 idle ）

求对给定任务一览进行安排，使得所用时间最少，求此时间。

Example:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
 
Constraints:
The number of tasks is in the range [1, 10000].
The integer n is in the range [0, 100].

　　

解法：

使用unordered_map来存放每个任务及其数量，求得最多的任务数maxcout，这里假设为 A

则有figure2和3两种情况。

figure2: 所有任务未占满，那么此时n+1=5，maxcout-1=3，再加上相同任务数量为maxcout的任务数（A，B）=3*5+2=17

figure3: 所有任务占满（没有空闲时间idle slot），那么直接等于nums.size()=19

参考代码：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char,int> tasksm;
        unordered_map<char,int>::iterator it;
        int maxcout=0;
        for(char i:tasks){
            tasksm[i]++;
            maxcout=max(maxcout, tasksm[i]);
        }
        int res=0;
        res = (n+1)*(maxcout-1);
        for(auto e:tasksm){
            if(e.second==maxcout) res++;
        }
        res = max(res, (int)tasks.size());
        return res;
    }
};