टास्क शेड्यूलर एन सी++

मान लीजिए कि हमारे पास एक चार सरणी है जो सीपीयू को करने वाले कार्यों का प्रतिनिधित्व करती है। इसमें अपरकेस अक्षर A से Z तक होते हैं जहाँ विभिन्न अक्षर विभिन्न कार्यों का प्रतिनिधित्व करते हैं। कार्यों को मूल आदेश के बिना किया जा सकता था। प्रत्येक कार्य एक अंतराल में किया जा सकता था। प्रत्येक अंतराल के लिए, CPU एक काम पूरा कर सकता है या बस निष्क्रिय हो सकता है। हालाँकि, एक गैर-नकारात्मक शीतलन अंतराल है जिसे n कहा जाता है, जिसका अर्थ है कि दो समान कार्यों के बीच, कम से कम n अंतराल होना चाहिए जो CPU अलग-अलग कार्य कर रहा हो या बस निष्क्रिय हो। हमें दिए गए सभी कार्यों को पूरा करने के लिए सीपीयू द्वारा लिए जाने वाले कम से कम अंतराल का पता लगाना होगा। तो अगर इनपुट [ए, ए, ए, बी, बी, बी] है और एन 2 है, तो आउटपुट 8 होगा, क्योंकि ए → बी → निष्क्रिय → ए → बी → निष्क्रिय → ए → बी

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मैप एम बनाएं, और टास्क ऐरे में स्टोर किए गए सभी वर्णों की फ़्रीक्वेंसी को स्टोर करें

• प्राथमिकता कतार pq परिभाषित करें

• m पर मौजूद प्रत्येक की-वैल्यू पेयर के लिए, pq में फ़्रीक्वेंसी मान डालें

• उत्तर:=0, चक्र:=n + 1

• जबकि pq खाली नहीं है

  • सरणी अस्थायी परिभाषित करें, समय निर्धारित करें:=0

  • क्योंकि मैं श्रेणी 0 में हूं और pq खाली नहीं है, और i - चक्र

    • पीक्यू के शीर्ष तत्व को अस्थायी में डालें, पीक्यू से शीर्ष हटाएं, 1 से तापमान बढ़ाएं

  • मेरे लिए 0 से लेकर तापमान के आकार तक की सीमा में है

    • तापमान कम करें[i] 1

    • अगर अस्थायी [i] 0 नहीं है, तो अस्थायी [i] को pq में डालें

  • उत्तर :=उत्तर + समय जब 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