작업 스케줄러 n C++

CPU가 수행해야 하는 작업을 나타내는 char 배열이 있다고 가정합니다. 여기에는 대문자 A ~ Z가 포함되며 다른 문자는 다른 작업을 나타냅니다. 작업은 원래 순서 없이 수행될 수 있습니다. 각 작업은 한 간격으로 수행할 수 있습니다. 각 간격에 대해 CPU는 하나의 작업을 완료하거나 그냥 유휴 상태일 수 있습니다. 그러나 두 개의 동일한 작업 사이에 n이라는 음수가 아닌 냉각 간격이 있습니다. 즉, CPU가 다른 작업을 수행하거나 그냥 유휴 상태인 간격이 최소 n개 있어야 합니다. CPU가 주어진 모든 작업을 완료하는 데 걸리는 최소 간격을 찾아야 합니다. 따라서 입력이 [A, A, A, B, B, B]이고 n이 2이면 출력은 A → B → 유휴 → A → B → 유휴 → A → B

와 같이 8이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

맵 m을 만들고 작업 배열에 저장된 모든 문자의 빈도를 저장합니다.
우선순위 대기열 pq 정의
m에 있는 각 키-값 쌍에 대해 pq에 빈도 값을 삽입합니다.
ans :=0, 주기 :=n + 1
pq가 비어 있지 않은 동안
- 어레이 온도 정의, 시간 설정 :=0
- 범위 0에 있는 i에 대해 pq는 비어 있지 않으며 i − 주기
  - pq의 맨 위 요소를 temp에 삽입하고 pq에서 맨 위를 삭제하고 temp를 1 증가
- 범위 0에서 온도 크기까지의 i에 대해
  - temp[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