Lập lịch nhiệm vụ trong C++

Cho mảng ký tự tasks (A-Z), mỗi nhiệm vụ mất 1 khoảng thời gian. Giữa 2 nhiệm vụ cùng loại phải có ít nhất n khoảng thời gian làm nhiệm vụ khác hoặc rảnh. Tìm số khoảng thời gian tối thiểu để hoàn thành tất cả.

Ví dụ: [A,A,A,B,B,B], n=2 → Kết quả: 8. Trình tự: A→B→idle→A→B→idle→A→B.

Giải thuật (Heap ưu tiên + Chu kỳ)

1. Đếm tần suất mỗi nhiệm vụ → map m.
2. Max-heap pq chứa tần suất.
3. cycle = n+1, ans = 0.
4. Khi pq không rỗng:
5. Lấy tối đa cycle nhiệm vụ tần suất cao nhất vào temp.
6. Giảm tần suất, push lại nếu > 0.
7. ans += pq.empty() ? time : cycle.
8. Trả về ans.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int leastInterval(vector<char>& t, int n) {
        map<char,int> m;
        for(char c : t) m[c]++;
        priority_queue<int> pq;
        for(auto &p : m) pq.push(p.second);
        int ans = 0, 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 x : temp) if(--x > 0) pq.push(x);
            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);
    return 0;
}

Đầu vào

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

Đầu ra

8