Bộ lập lịch tác vụ n C ++

Giả sử chúng ta có một mảng char thể hiện các tác vụ CPU cần thực hiện. Điều này chứa các chữ cái viết hoa từ A đến Z trong đó các chữ cái khác nhau đại diện cho các nhiệm vụ khác nhau. Các nhiệm vụ có thể được thực hiện mà không có thứ tự ban đầu. Mỗi nhiệm vụ có thể được thực hiện trong một khoảng thời gian. Đối với mỗi khoảng thời gian, CPU có thể hoàn thành một công việc hoặc chỉ ở chế độ nhàn rỗi. Tuy nhiên, có một khoảng thời gian làm mát không âm được gọi là n có nghĩa là giữa hai tác vụ giống nhau, phải có ít nhất n khoảng thời gian mà CPU đang thực hiện các tác vụ khác nhau hoặc chỉ ở chế độ nhàn rỗi. Chúng ta phải tìm số khoảng thời gian ít nhất mà CPU sẽ thực hiện để hoàn thành tất cả các tác vụ đã cho. Vì vậy, nếu đầu vào là [A, A, A, B, B, B] và n là 2, thì đầu ra sẽ là 8, như A → B → nhàn rỗi → A → B → nhàn rỗi → A → B

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Tạo một bản đồ m và lưu trữ tần số của tất cả các ký tự được lưu trữ trong mảng tác vụ
Xác định hàng đợi ưu tiên pq
đối với mỗi cặp khóa-giá trị có tại m, hãy chèn các giá trị tần số vào pq
ans:=0, chu kỳ:=n + 1
trong khi pq không trống
- xác định nhiệt độ mảng, đặt thời gian:=0
- đối với tôi trong phạm vi 0 và pq không trống, và i - chu kỳ
  - chèn phần tử trên cùng của pq vào tạm thời, xóa phần trên khỏi pq, tăng nhiệt độ lên 1
- cho tôi trong phạm vi từ 0 đến kích thước của nhiệt độ
  - giảm nhiệt độ [i] xuống 1
  - nếu temp [i] không phải là 0, thì hãy chèn temp [i] vào pq
- ans:=ans + thời gian khi pq trống, nếu không thì chu kỳ
trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#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)) ;
}

Đầu vào

{'A','A','A','B','B','B'}
2

Bộ lập lịch tác vụ n C ++

Ví dụ (C ++)

Đầu vào

Đầu ra