数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 任务调度器
假设我们有一个字符数组，表示 CPU 需要执行的任务。该数组包含大写字母 A 到 Z，不同的字母代表不同的任务。任务可以不必按照原始顺序执行。每个任务可以在一个时间间隔内完成。在每个时间间隔内，CPU 可以完成一项工作或保持空闲。但是，存在一个非负冷却间隔 n，这意味着两次执行相同任务之间，必须至少有 n 个时间间隔 CPU 执行不同的任务或保持空闲。我们需要找到 CPU 完成所有给定任务所需的最小时间间隔数。例如，如果输入是 [A, A, A, B, B, B] 且 n 为 2，则输出为 8，因为执行顺序为 A → B → 空闲 → A → B → 空闲 → A → B
为了解决这个问题，我们将遵循以下步骤：
创建一个映射 m，存储任务数组中所有字符的频率。
定义一个优先级队列 pq。
对于 m 中的每个键值对，将频率值插入 pq。
ans := 0，cycle := n + 1
当 pq 不为空时
定义一个数组 temp，设置 time := 0
对于 i 的范围为 0 到 pq 不为空且 i < cycle
将 pq 的顶部元素插入 temp，从 pq 中删除顶部元素，将 time 加 1
对于 i 的范围为 0 到 temp 的大小
将 temp[i] 减 1
如果 temp[i] 不为 0，则将 temp[i] 插入 pq
当 pq 为空时，ans := ans + time；否则 ans := ans + cycle
返回 ans
示例 (C++)
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int leastInterval(vector<char>& t, int n) {
map <char,int> m;
for(int i =0;i<t.size();i++){
m[t[i]]++;
}
map <char, int> :: iterator i = m.begin();
priority_queue <int> pq;
while(i != m.end()){
pq.push(i->second);
i++;
}
int ans = 0;
int cycle = n + 1;
while(!pq.empty()){
vector <int> temp;
int time = 0;
for(int i = 0; !pq.empty() && i < cycle; i++){
temp.push_back(pq.top());
pq.pop();
time++;
}
for(int i = 0;i < temp.size(); i++){
temp[i]-- ;
if(temp[i])pq.push(temp[i]);
}
ans += pq.empty()? time : cycle;
}
return ans;
}
};
main(){
vector<char> v = {'A','A','A','B','B','B'};
Solution ob;
cout << (ob.leastInterval(v, 2)) ;
}输入
{'A','A','A','B','B','B'}
2输出
8
更新于：2020年4月30日
3K+ 次浏览
广告