ตัวกำหนดเวลางาน n C++

สมมติว่าเรามีอาร์เรย์ถ่านที่แสดงถึงงานที่ CPU ต้องทำ ประกอบด้วยตัวพิมพ์ใหญ่ A ถึง Z โดยที่ตัวอักษรต่างกันแสดงถึงงานที่แตกต่างกัน งานสามารถทำได้โดยไม่ต้องมีคำสั่งเดิม แต่ละงานสามารถทำได้ในช่วงเวลาเดียว สำหรับแต่ละช่วงเวลา CPU สามารถทำงานหนึ่งงานให้เสร็จหรือไม่ได้ใช้งาน อย่างไรก็ตาม มีช่วงการระบายความร้อนที่ไม่เป็นลบที่เรียกว่า n ซึ่งหมายถึงระหว่างงานเดียวกันสองงาน ต้องมีอย่างน้อย n ช่วงที่ CPU กำลังทำงานที่แตกต่างกันหรือเพียงแค่ไม่ได้ใช้งาน เราต้องหาช่วงเวลาให้น้อยที่สุดที่ CPU จะใช้เพื่อทำงานที่กำหนดทั้งหมดให้เสร็จ ดังนั้นหากอินพุตคือ [A, A, A, B, B, B] และ n คือ 2 เอาต์พุตจะเป็น 8 เช่น A → B → idle → A → B → idle → A → B

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างแผนที่ m และเก็บความถี่ของอักขระทั้งหมดที่เก็บไว้ในอาร์เรย์งาน

• กำหนดลำดับความสำคัญ pq

• สำหรับคู่คีย์-ค่าแต่ละคู่ที่ m ให้แทรกค่าความถี่ลงใน pq

• ตอบ :=0, รอบ :=n + 1

• ในขณะที่ pq ไม่ว่างเปล่า

  • กำหนดอาร์เรย์ชั่วคราว ตั้งเวลา :=0

  • สำหรับฉันในช่วง 0 และ pq ไม่ว่างเปล่า และ i – รอบ

    • แทรกองค์ประกอบบนสุดของ pq ลงใน temp, ลบ top จาก pq, เพิ่ม temp ขึ้น 1

  • สำหรับผมอยู่ในช่วง 0 ถึงขนาดของอุณหภูมิ

    • ลดอุณหภูมิ[i] 1

    • ถ้า temp[i] ไม่ใช่ 0 ให้ใส่ temp[i] ลงใน pq

  • 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

ผลลัพธ์

8