ধরুন আমাদের কাছে একটি অক্ষর অ্যারে রয়েছে যা সিপিইউকে করতে হবে এমন কাজগুলিকে উপস্থাপন করে৷ এতে A থেকে Z পর্যন্ত বড় হাতের অক্ষর রয়েছে যেখানে বিভিন্ন অক্ষর বিভিন্ন কাজের প্রতিনিধিত্ব করে। কাজগুলি মূল আদেশ ছাড়াই করা যেতে পারে। প্রতিটি কাজ এক বিরতিতে করা যেতে পারে। প্রতিটি ব্যবধানের জন্য, CPU একটি কাজ শেষ করতে পারে বা কেবল নিষ্ক্রিয় থাকতে পারে। যাইহোক, n নামক একটি নন-নেগেটিভ কুলিং ইন্টারভাল আছে যার অর্থ দুটি একই কাজের মধ্যে, অন্তত n ব্যবধান থাকতে হবে যে CPU বিভিন্ন কাজ করছে বা শুধু নিষ্ক্রিয়। প্রদত্ত সমস্ত কাজ শেষ করার জন্য সিপিইউ-এর ন্যূনতম সংখ্যক ব্যবধান আমাদের খুঁজে বের করতে হবে। সুতরাং যদি ইনপুট হয় [A, A, A, B, B, B] এবং n হয় 2, তাহলে আউটপুট হবে 8, যেমন A → B → নিষ্ক্রিয় → A → B → নিষ্ক্রিয় → A → B
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র m তৈরি করুন এবং টাস্ক অ্যারেতে সংরক্ষিত সমস্ত অক্ষরের ফ্রিকোয়েন্সি সংরক্ষণ করুন
-
অগ্রাধিকার সারি pq
সংজ্ঞায়িত করুন -
m-এ উপস্থিত প্রতিটি কী-মানের জোড়ার জন্য, pq
-এ ফ্রিকোয়েন্সি মান সন্নিবেশ করান -
উত্তর :=0, চক্র :=n + 1
-
যখন pq খালি থাকে না
-
অ্যারে তাপমাত্রা সংজ্ঞায়িত করুন, সময় সেট করুন :=0
-
0 এবং pq পরিসরে i এর জন্য খালি নয়, এবং i − চক্র
-
টেম্প-এ pq-এর টপ এলিমেন্ট সন্নিবেশ করান, pq থেকে টপ ডিলিট করুন, 1 দ্বারা টেম্প বাড়ান
-
-
আমি 0 থেকে টেম্পের আকারের মধ্যে
-
তাপমাত্রা [i] 1 দ্বারা কমান
-
যদি temp[i] 0 না হয়, তাহলে pq
-এ temp[i] ঢোকান
-
-
ans :=ans + সময় যখন pq খালি থাকে, অন্যথায় চক্র
-
-
উত্তর ফেরত দিন
উদাহরণ(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
