Description

给你一个用字符数组\(tasks\)表示的CPU需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在\(1\)个单位时间内执行完。在任何一个单位时间，CPU可以完成一个任务，或者处于待命状态。

然而，两个相同种类的任务之间必须有长度为整数\(n\)的冷却时间，因此至少有连续\(n\)个单位时间内CPU在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

Constraints

  • \(1 \le task.length \le 10^4\)
  • \(0 \le n \le 100\)

Solution

一个基本的思路就是字符轮流贪心取，没办法再待命

具体到数据结构上，用2个堆来维护，一个大根堆维护\(\{cnt, char\}\)，另一个小根堆维护\(\{d, cnt, char\}\)。其中\(char\)表示字符，\(cnt\)表示剩余次数，\(d\)表示冷却到达时间。每次从大根堆消费一个字符后就算好对应的\(d\)并放入小根堆\(\{d, cnt-1, char\}\)，下一次消费再尝试捞出来

复杂度\(O(nlogn)\)，这里\(n\)表示\(task\)的长度

Code

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        using Tup2 = std::tuple<int, char>;
        using Tup3 = std::tuple<int, int, char>;
        auto pcnt = priority_queue<Tup2> {};
        auto pduration
            = priority_queue<Tup3, vector<Tup3>, greater<Tup3>> {};
        int cnt[128] {};
        for(auto t : tasks) cnt[t]++;
        for(int i = 0; i < 128; ++i) {
            // NOTE
            if(!cnt[i]) continue;
            pcnt.emplace(cnt[i], i);
        }
        int consumed = 0;
        int clock = 0;
        while(consumed < tasks.size()) {
            while(!pduration.empty()) {
                auto [d, c, a] = pduration.top();
                if(clock < d) break;
                pduration.pop();
                pcnt.emplace(c, a);
            }
            if(!pcnt.empty()) {
                auto [c, a] = pcnt.top();
                pcnt.pop();
                consumed++;
                if(--c > 0) {
                    pduration.emplace(clock + n + 1, c, a);
                }
            }

            if(pcnt.empty() && !pduration.empty()) {
                clock = get<0>(pduration.top());
            } else {
                clock++;
            }
        }
        return clock;
    }
};

LeetCode-621 Task Scheduler