621. Task Scheduler -M

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.

Note:

1. The number of tasks is in the range [1, 10000].
2. The integer n is in the range [0, 100].

A:

思路是：首先对每个出现的task 计算出先的次数。
然后每次有限安排出现次数最多的task. -------但是这样是最优的吗？？？？？？因此，不能直接减去res += (n+1) * V[n]   然后 V[i] -= V[n]  这样得不到最优解。因为一次减去的太多，下次可能已经不是最高的了。
如果task 数小于n+1， 则按照最多的那个，计算， （最后一次可能不满，因此要分开单独计算）

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> M;
        for(auto ch: tasks)
            M[ch]++;
        vector<int> V;
        for(auto& t:M)
            V.push_back(t.second);
        int res = 0;
        sort(V.begin(), V.end(), greater<>());
        while(not V.empty())
        {
            if(V.size() >= n+1)
            {
                res += n+1;//!!!!!!!!!!!!!This is the key, need to update one-by-one
                for(int i =0;i<= n; ++i)
                    V[i] -= 1;
                
                sort(V.begin(), V.end(), greater<>() );// default is in assending order
                while(not V.empty() and V.back()==0)
                    V.pop_back();
            }else{
                res += (n+1) * (V[0]-1); // all iteration round (with idle)
                res++; // add first v[0]
                for(int i =1; i<V.size(); ++i)
                {
                    if(V[i] == V[0])
                        res++;
                    else
                        break;
                }
                V.clear();
            }   
        }
        return res;
    }
};

----------更优的解法 看https://leetcode.com/problems/task-scheduler/solution/  解法3

对每个task， 看其idle 个数。 （也就是上面的else 里的情况）

Learned:

1:  local variable must be clearly initialized . 
       int res;   一开始没有初始化，在remote 编译器里，就总是fail