Task Scheduler

https://leetcode.com/problems/task-scheduler/description/

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 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

The number of tasks is in the range [1, 10000].

The integer n is in the range [0, 100].

Thoughts

给一堆字母，每两个相同字母相隔至少为n，问装下所有字母至少需要多少长度的数组。思路和Rearrange String k Distance Apart一致，贪心，对i从能放在i的可选字符中选剩下数目最多放入。(最高频率 - 1) * (n + 1)统计了为满足最高频率的元素间隔要求至少需要的元素数，间隔内插入其它元素，最后再剩余元素: 和最高频率相同的字符。当间隔空间不足以充满所有元素时直接硬撑，此时频率最高的已满足，其它的更满足，所需最短长度为N，不需要任何额外元素。

Code

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        const int N = tasks.size();
        vector<int> freqs(26, 0);
        int mx_cnt = 0;
        for (auto t : tasks) {
            t -= 'A';
            ++freqs[t];
            mx_cnt = max(mx_cnt, freqs[t]);
        } 
        int same_mx_cnt = 0;
        for (const auto c : freqs) {
            if (c == mx_cnt) ++same_mx_cnt;
        } 
        const int r = (n + 1) * (mx_cnt - 1) + same_mx_cnt;
        return r > N ? r : N;
    }
};

Analysis

时间复杂度O(N),