C++で解くジョブスケジュールの最小難易度問題

問題概要

d日間でタスクのリストをスケジューリングすることを考えます。タスクには依存関係があり、i番目のタスクに取り掛かるためには、0 <= j < i を満たすすべてのタスク j を先に完了させておく必要があります。

さらに、毎日最低1つはタスクを完了させなければなりません。スケジュール全体の難易度は、d日間の各日の難易度の合計として定義され、ある日の難易度は、その日に完了したタスクの中で最も高い難易度の値となります。

ここで、整数型配列 taskDifficulty と整数 d が与えられます。i番目のタスクの難易度は taskDifficulty[i] です。スケジュール全体の難易度の最小値を求めてください。スケジュールが構成できない場合は -1 を返します。

入力例と出力例

たとえば、taskDifficulty = [6,5,4,3,2,1]、d = 2 が入力された場合を考えてみましょう。

このとき出力は 7 になります。1日目に最初の5つのタスクを処理すると、その日の難易度は区間の最大値である 6。2日目に残りの1つのタスクを処理すると、難易度は 1 です。したがって、スケジュール全体の難易度は 6 + 1 = 7 となります。

解法のアプローチ

この問題は、動的計画法(DP)とメモ化再帰を組み合わせることで効率的に解けます。手順は以下の通りです。

• solve() 関数を定義します。引数は配列 v、現在のインデックス idx、残り日数 k、二次元配列 dp です。
• idx が配列 v のサイズと等しく、かつ k が 0 の場合は 0 を返します(全タスクを指定日数内で完了できた状態)。
• k < 0 の場合、または idx が配列サイズに達していて k > 0 の場合は、大きな値(1e6)を返します(無効な状態)。
• dp[idx][k] が -1 以外の場合、すでに計算済みなのでその値を返します。
• maxVal を 0、ret を INT_MAX で初期化します。
• i を idx から配列末尾までループさせます。
  • maxVal を v[i] との最大値で更新します(idx〜i 区間の最大難易度を保持)。
  • ret を「maxVal + solve(v, i + 1, k - 1, dp)」との最小値で更新します。
• 結果を dp[idx][k] に記録して返します。

メイン関数での処理

• n をタスクの総数とします。
• d > n の場合、毎日1つ以上のタスクを処理する条件を満たせないため -1 を返します。
• サイズ n × (d + 1) の二次元配列 dp を作成し、すべて -1 で初期化します。
• solve(j, 0, d, dp) の結果を返します。

このアルゴリズムの時間計算量は O(n² × d)、空間計算量は O(n × d) です。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(vector<int>& v, int idx, int k, vector<vector<int> >&
    dp){
       if (idx == v.size() && k == 0)
       return 0;
       if (k < 0 || idx == v.size() && k > 0)
       return 1e6;
       if (dp[idx][k] != -1)
       return dp[idx][k];
       int maxVal = 0;
       int ret = INT_MAX;
       for (int i = idx; i < v.size(); i++) {
           maxVal = max(v[i], maxVal);
           ret = min(ret, maxVal + solve(v, i + 1, k - 1, dp));
       }
       return dp[idx][k] = ret;
   }
    int minDifficulty(vector<int>& j, int d){
       int n = j.size();
       if (d > n)
       return -1;
       vector<vector<int> > dp(n, vector<int>(d + 1, -1));
       return solve(j, 0, d, dp);
   }
};
main(){
    Solution ob;
    vector<int> v = {6,5,4,3,2,1};
    cout << (ob.minDifficulty(v, 2));
}

入力

{6,5,4,3,2,1}, 2

出力

7