C++で解くタスクスケジューラ問題：クールダウン間隔nを考慮した最小実行インターバル数の求め方

問題概要

CPUが実行すべきタスクを表すchar型の配列を考えます。この配列には大文字A〜Zが含まれ、異なる文字はそれぞれ異なるタスクを表します。タスクは元の順序にとらわれず任意の順番で実行でき、1つのタスクは1インターバル（単位時間）で完了します。各インターバルにおいて、CPUは1つのタスクを実行するか、アイドル状態になるかのどちらかです。

ここで重要になるのが、非負整数のクールダウン間隔 nです。これは、同じタスクを2回実行する間には、少なくともn個のインターバル（別のタスクの実行またはアイドル時間）を挟む必要があるという制約を意味します。この条件下で、与えられたすべてのタスクを完了させるのに必要な最小インターバル数を求めましょう。

例：入力が [A, A, A, B, B, B] で n = 2 の場合、答えは 8 となります。
A → B → idle → A → B → idle → A → B
同じA同士の間には2つ以上のインターバルが必要ですが、Bは3回しかないため、空いてしまったインターバルにはアイドルを挿入する必要があります。

解法のアプローチ（貪欲法＋優先度付きキュー）

この問題は「残り出現回数が最も多いタスクから優先的に実行する」という貪欲法で解けます。頻度の高いタスクを早めに消化することで、クールダウンによる待ち時間を最小化できるためです。具体的な手順は以下の通りです。

1. マップ m を作成し、タスク配列に含まれる各文字の出現回数を記録します。
2. 優先度付きキュー（最大ヒープ）pq を用意します。
3. m 内の各キーと値のペアについて、出現回数を pq に挿入します。
4. 答え ans を 0、サイクル長 cycle を n + 1 で初期化します。
5. pq が空でない限り、次の処理を繰り返します。
   • 一時配列 temp を用意し、経過時間 time を 0 に設定します。
   • i が cycle 未満かつ pq が空でない間、pq の先頭（最大値）を temp に移し、time を1増やします。
   • temp の各要素から1を減算し、値が0でなければ pq に戻します。
   • pq が空になった場合は ans += time、まだタスクが残っている場合は ans += cycle とします。
6. 最終的に ans を返します。

ポイントは cycle = n + 1 としている点です。同じタスクを再実行するまでに n 個の別タスクまたはアイドルが必要なため、1サイクルあたり最大 n + 1 種類のタスクを実行できます。そして、pq が空になった直前のサイクルでは、実際に実行したタスク数 time だけを加算することで、余分なアイドル時間をカウントせずに済みます。

計算量

• 時間計算量：O(N log N)（Nはタスク総数。各タスクをヒープに挿入・削除するため）
• 空間計算量：O(K)（Kはタスクの種類数。本問では最大26）

C++での実装例

理解を深めるため、上記アルゴリズムの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

このように、優先度付きキューを使って頻度の高いタスクから順に処理することで、クールダウン制約を満たしつつ、全タスクを最小のインターバル数で完了させることができます。