ตัวจัดตารางงาน (Task Scheduler) ใน C++

สมมติว่าเรามีอาร์เรย์ตัวอักษรแทนงานที่ CPU ต้องทำ ตัวอักษร A-Z แทนงานต่างกัน งานทำได้ในลำดับไหนก็ได้ แต่ละงานใช้ 1 interval ระหว่างงานชนิดเดียวกัน ต้องมี interval อื่นหรือ idle อย่างน้อย n ช่วง (cooling interval) หาจำนวน interval น้อยที่สุดเพื่อทำงานทั้งหมด

ตัวอย่าง: [A,A,A,B,B,B], n=2 ผลลัพธ์: 8
ลำดับ: A → B → idle → A → B → idle → A → B

ขั้นตอนการแก้ปัญหา (Greedy + Max Heap)

• นับความถี่ของแต่ละงาน เก็บในแผนที่ m
• สร้าง Max Heap (Priority Queue) ใส่ความถี่ทั้งหมด
• ans := 0, cycle := n + 1
• while PQ ไม่ว่าง:
  • temp := [], time := 0
  • วน i จาก 0 ถึง cycle-1 และ PQ ไม่ว่าง:
    • ดึงค่าสูงสุดออกจาก PQ ใส่ temp เพิ่ม time
  • ลดค่าใน temp ลง 1 ถ้ายัง > 0 ใส่กลับเข้า PQ
  • ans += (PQ ว่าง ? time : 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]]++;
        }
        priority_queue <int> pq;
        for(auto &p : m) {
            pq.push(p.second);
        }
        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;
    }
};

int 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