小楼一夜听春雨
深巷明朝卖杏花
C++，暴力排序模拟和桶排序。
暴力排序模拟
一开始想到的就是模拟了，直接模拟整个CPU执行任务的过程，用一个循环变量i标记CPU的每次执行，然后记住每种任务执行对应的i的值，每次取新任务的时候，都对任务数组重新排序，从最繁忙的任务开始，找到一个满足前n次都没执行过的任务，执行并标记为执行。。。
暴力模拟的思路很简单，代码一般会稍微麻烦点，还有就是复杂度不优。
class Solution {
public:
struct Node {
int pre;
int cnt;
};
static bool cmp(Node a, Node b) {
return a.cnt > b.cnt;
}
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char, int> hash;
for (const char &it : tasks) hash[it]++;
vector<Node> ns;
for (const auto &it : hash) {
Node temp = {-101, it.second};
ns.push_back(temp);
}
bool flag = false;
int i = 0, ans = 0;
do {
bool is_free = true;
flag = false;
sort(ns.begin(), ns.end(), cmp);
for (Node &it : ns) {
if (it.cnt) flag = true;
if (it.pre + n < i && it.cnt) {
it.cnt--;
it.pre = i;
is_free = false;
break;
}
}
i++;
if (is_free && flag)
ans++;
} while (flag);
return ans + tasks.size();
}
};
桶排序
桶排序的思路是参考了题解中一位大佬说的，其实很多题解解释了很多，都没有桶排序三个字来得直观。题解里用到的公式： \(total = (maxcnt - 1) * (n - 1) + s\) 其实用桶排序的思想解释，会很直观的，total就是最少的执行次数，maxcnt就是频次最高的任务的频次，s是最后桶中的任务数目。
桶思想-简洁高效：我们设计桶的大小为 n+1，则相同的任务恰好不能放入同一个桶，最密也只能放入相邻的桶。
对于重复的任务，我们只能将每个都放入不同的桶中，因此桶的个数就是重复次数最多的任务的个数。
一个桶不管是否放满，其占用的时间均为 n+1，这是因为后面桶里的任务需要等待冷却时间。最后一个桶是个特例，由于其后没有其他任务需等待，所以占用的时间为桶中的任务个数。
最终我们得到：
总排队时间 = (桶个数 - 1) * (n + 1) + 最后一桶的任务数。
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> hash(26, 0);
for (const uint8_t &it : tasks)
hash[it - 'A']++;
int maxcnt = *max_element(hash.begin(), hash.end());
int ans = (maxcnt - 1) * (n + 1);
for (const int &it : hash) {
if (it == maxcnt)
ans++;
}
return ans > tasks.size() ? ans : tasks.size();
}
};
要说明的是，s其实就是频次等于maxcnt的任务种类数。
