题目描述

这题居然是medium。。。

算法1

贪心 $O(n)$

C++ 代码

    // 核心思想是 最后需要的 #slot 等于 #tasks + #idles

    // 找出 most frequent task，假设是A，个数是count(A)
    // 有可能 most frequent task不止一个，假如有k个，比如k=2，有2个task，AB，都出现count(A)次
    // 将AB依次排开，构成count(A)-1个区间

    // 例如，tasks = 3 A, 3 B, 2 C, 1 D
    // A B _ _ A B _ _ A B

    // 下面计算要填充多少个idle tasks。

    // 每个区间有多少个empty slots？ most frequent task，除了A外，都要放在区间里，
    // 所以每个区间还剩 n-(k-1) 个empty slots

    // 这些区间一共有多少个empty slots？有 #empty_slots = ( count(A)-1 ) *（n-k+1）

    // 除了出现次数最多的tasks，A和B，还有多少要处理的tasks？ #available_tasks = #tasks - k*count(A)
    // 需要填充多少个idle task？#idles = #empty_slots - #available_tasks

    // 如果 #available_tasks > #empty_slots，则不需要填充 idle task
    // 所以，#idles = max(0, #empty_slots - #available_tasks)

    // 一共需要多少slots？ #task + #idles

    // 例外情况，如果 most frequent task 大于n+1个， k>n+1 -> n-k+1<0，则每个区间没有empty slots，但此时每个区间可扩充到容纳不同的task，而不需要填idle task，一共需要#tasks个slots

    int leastInterval(vector<char>& tasks, int n) {
        // 找出most frequent tasks
        vector<int> count(26, 0);
        for(auto c : tasks) count[c-'A'] ++;

        int mx = 0, n_mx = 0;
        for(int i=0; i<26; i++) {
            if(count[i] > mx) {
                mx = count[i];
                n_mx = 1;
            } else if(count[i] == mx) {
                n_mx ++;
            }
        }

        int n_empty_slots = (mx-1) * (n - (n_mx-1) );
        if(n_empty_slots < 0) return tasks.size();

        int n_available_tasks = tasks.size() - mx * n_mx;
        int n_idles = max(0, n_empty_slots - n_available_tasks);

        return tasks.size() + n_idles;
    }

算法2

heap, $O(n)$

C++ 代码

    // 用hashtable求每个task的数量
    // 用max-heap存task，每一轮，从heap中取n+1个task来处理
    // 每个task处理后计数减1，如果不为0，该轮结束后，再放入heap中
    // 当heap中task个数小于n时，用idle填充
    // 对最后一轮，只需要加实际处理的task数量

    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> hash;
        for(auto c : tasks) hash[c]++;

        // max heap
        using TPair = pair<char, int>; // task, count
        priority_queue<TPair, vector<TPair>,
            function<bool(const TPair& a, const TPair& b)>>
                pq( [](const TPair& a, const TPair& b) {
                    return b.second > a.second;
                });

        for(auto& kv : hash) pq.push(kv);

        int res = 0;
        while(pq.size()) {
            int sz = pq.size();
            // 有多于 n+1个task要处理
            if(sz >= n+1) {
                vector<TPair> tmp; //暂存处理后仍不为0的task
                for(int i=0; i<n+1; i++) {
                    auto task = pq.top();
                    pq.pop();
                    task.second--;
                    if(task.second != 0) tmp.push_back(task);
                }
                // 将未处理完的task放回heap
                for(auto& task : tmp) pq.push(task);

                res += (n+1);

            } else { // 少于n+1个task要处理，要用idle填充
                vector<TPair> tmp;
                for(int i=0; i<sz; i++) {
                    auto task = pq.top();
                    pq.pop();
                    task.second--;
                    if(task.second != 0) tmp.push_back(task);
                }
                // 如果tmp.size==0，所有task都已经处理完了，不需要填idle
                // 否则，要填idle到n+1
                if(tmp.size()==0) {
                    res += sz; // while(pq.size()) 将结束
                }
                else {
                    for(auto& task: tmp) pq.push(task);
                    res += (n+1);
                }                    
            }
        }
        return res;
    }