621. Task Scheduler

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].

先統計一下出現各個task出現的次數，找出出現次數最多的task還有數量。以題目提供的例子來想，A出現3次，B也出現3次。理想上我們會想把A隔得越遠越好。 A ? ? A ? ? A 中間?號代表可能的idle slots。 但這題出現3次的task不只A還有B。所以我們可以讓B用相同的模式填入。 A B ? A B ? A B 最後可以看成AB是一個合在一起的一個區塊。 AB ? AB ? AB --> X ? X ? X, where X is AB. Implementation可以先算出總idle slots數量然後減掉available tasks，這樣可以算出最後需要的idle slots，最後再加上原本的tasks總量就是所求。

int leastInterval(vector<char>& tasks, int n) { // time: O(N); space: O(1)
    vector<int> count(26, 0);
    int mx = 0, maxCount = 0;
    for (char task : tasks) {
        ++count[task - 'A'];
        if (mx == count[task - 'A']) {
            ++maxCount;
        } else if (mx < count[task - 'A']) {
            mx = count[task - 'A'];
            maxCount = 1;
        }
    }
    int partCount = mx - 1;
    int partLength = n - (maxCount - 1);
    int emptySlots = partCount * partLength;
    int availableTasks = tasks.size() - mx * maxCount;
    int idles = max(0, emptySlots - availableTasks);
    return tasks.size() + idles;
    // return max((int)tasks.size(), (mx - 1) * (n + 1) + maxCount);
}

int leastInterval(vector<char>& tasks, int n) { // time: O(NlogN); space: O(1)
    vector<int> cnt(26, 0);
    for (char c : tasks) ++cnt[c - 'A'];
    sort(cnt.begin(), cnt.end());
    int i = 25, mx = cnt[25], len = tasks.size();
    while (i >= 0 && cnt[i] == mx) --i;
    // (mx - 1): the number of complete partions
    // (n + 1): length of each partition
    // (25 - i): the number of tasks with the max occurrence times
    return max(len, (mx - 1) * (n + 1) + (25 - i));
}

int leastInterval(vector<char>& tasks, int n) { // time: O(NlogN); space: O(1)
    vector<int> count(26, 0);
    for (char task : tasks) ++count[task - 'A'];
    sort(count.begin(), count.end());
    int max_val = count[25] - 1, idle_slots = max_val * n;
    for (int i = 24; i >= 0 && count[i] > 0; --i) {
        idle_slots -= min(max_val, count[i]);
    }
    return tasks.size() + (idle_slots > 0 ? idle_slots : 0);
}

int leastInterval(vector<char>& tasks, int n) { // time: O(NlogN); space: O(N)
    vector<int> count(26, 0);
    for (char task : tasks) ++count[task - 'A'];
    priority_queue<int> pq;
    for (int cnt : count) {
        if (!cnt) continue;
        pq.push(cnt);
    }
    int res = 0, cycle = n + 1;
    while (!pq.empty()) {
        vector<int> tmp;
        for (int i = 0; i < cycle; ++i) {
            if (!pq.empty()) {
                tmp.push_back(pq.top());
                pq.pop();
            }
        }
        for (auto& t : tmp) {
            if (--t) pq.push(t);
        }
        res += pq.empty() ? tmp.size() : cycle;
    }
    return res;
}

358. Rearrange String k Distance Apart767. Reorganize String