資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告