C++-এ টাস্ক শিডিউলার

মনে করুন একটি ক্যারেক্টার অ্যারে আছে যা CPU-র করা টাস্কগুলকে রিপ্রেজেন্ট করে। এতে বড় হাতের অক্ষর A থেকে Z থাকে যেখানে ভিন্ন অক্ষর ভিন্ন টাস্ক রিপ্রেজেন্ট করে। টাস্কগুলো অরিজিনাল অর্ডার ছাড়াও করা যেতে পারে। প্রতিটি টাস্ক একটি ইন্টারভালে করা যায়। প্রতিটি ইন্টারভালে CPU একটি কাজ খতম করতে পারে অথবা আইডল থাকতে পারে। তবে, একটি নন-নেগেটিভ কুলিং ইন্টারভাল `n` আছে যার মানে হলো একই দুটি টাস্কের মধ্যে কমপক্ষে `n`টি ইন্টারভাল থাকতে হবে যেখানে CPU অন্য টাস্ক করছে বা আইডল। আমাদের CPU সকল টাস্ক খতম করার জন্য ন্যূনতম ইন্টারভাল সংখ্যা বের করতে হবে। যদি ইনপুট `[A, A, A, B, B, B]` এবং `n` = 2 হয়, তবে আউটপুট হবে ৮, কারণ A → B → idle → A → B → idle → A → B।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

একটি ম্যাপ `m` তৈরি করুন, এবং টাস্ক অ্যারেতে সব ক্যারেক্টারের ফ্রিকোয়েন্সি স্টোর করুন
একটি প্রায়োরিটি কিউ `pq` সংজ্ঞায়িত করুন
`m`-এ উপস্থিত প্রতিটি কি-ভ্যালু পেয়ারের জন্য, ফ্রিকোয়েন্সি ভ্যালুগুলো `pq`-তে ইনসার্ট করুন
`ans := 0`, `cycle := n + 1`
যখন `pq` খালি না থাকে
- `temp` নামক একটি অ্যারে, `time := 0` সংজ্ঞায়িত করুন
- `i` = 0 এবং `pq` খালি না থাকে এবং `i < cycle` পর্যন্ত
  - `pq`-এর টপ এলিমেন্ট `temp`-এ ইনসার্ট করুন, `pq`-থেকে টপ ডিলিট করুন, `time` ১ বাড়ান
- `i` = 0 থেকে `temp`-এর আকার পর্যন্ত
  - `temp[i]` ১ কমান
  - যদি `temp[i]` 0 না হয়, তবে `temp[i]`-কে `pq`-তে ইনসার্ট করুন
- `ans := ans + time` যদি `pq` খালি থাকে, অন্যথায় `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