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, साइकिल := n + 1
• जब तक pq खाली नहीं है
  • टेम्प नामक ऐरे परिभाषित करें, टाइम := 0 सेट करें
  • i के लिए 0 और pq खाली नहीं है, और i - साइकिल की रेंज में
    • pq के टॉप एलिमेंट को टेम्प में डालें, pq से टॉप डिलीट करें, टेम्प को 1 से बढ़ाएं
  • i के लिए 0 से टेम्प के आकार तक की रेंज में
    • टेम्प[i] को 1 से घटाएं
    • यदि टेम्प[i] 0 नहीं है, तो टेम्प[i] को pq में डालें
  • ans := ans + टाइम जब pq खाली है, अन्यथा साइकिल
• 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