C++で解くジョブスケジューリング問題：重複しないタスク選択による最大利益の求め方

問題の概要

n個の異なるタスクがあるとします。各タスクiは startTime[i] から endTime[i] まで実行され、完了すると profit[i] の利益が得られます。startTime・endTime・profit の3つのリストが与えられたとき、実行時間帯が互いに重ならないようなタスクの部分集合の中で、得られる利益の合計が最大になる値を求めてください。

なお、あるタスクが時刻Xに終了する場合、同じ時刻Xに開始する別のタスクを選ぶことは可能です（終了時刻と開始時刻が一致していても重複とはみなしません）。

入力例

startTime = [1,2,3,3]、endTime = [3,4,5,6]、profit = [500,100,400,700]

この場合、出力は 1200 となります。これは、(1〜3, 利益500) のタスクと (3〜6, 利益700) のタスクを選択した組み合わせが最適だからです。

解法のアプローチ

この問題は「動的計画法（DP）」と「二分探索」を組み合わせることで効率的に解けます。基本的な考え方は次のとおりです。

• すべてのタスクを終了時刻の昇順にソートする。
• dp[i] を「i番目までのタスクから得られる最大利益」と定義する。
• 各タスクについて、そのタスクを「選ぶ場合」と「選ばない場合」の利益を比較し、大きい方を採用する。
• タスクを選ぶ場合、現在のタスクの開始時刻以前に終了する直前のタスクを二分探索で見つけ、その時点での最大利益を加算する。

アルゴリズムの手順

1. start（開始時刻）、end（終了時刻）、cost（利益）の3つの値を持つ構造体 Data を定義します。
2. Data 型の配列 j を作成し、入力の各タスクを格納します。
3. 配列 j を終了時刻を基準にソートします。
4. サイズ n の DP 配列 dp を定義し、dp[0] = j[0].cost で初期化します。
5. i = 1 から n-1 まで以下を繰り返します。
   • low = 0、high = i - 1 として二分探索を行い、「j[i].start 以降に終了する最初のタスク」の位置を特定します。
   • dp[i] = j[i].cost とし、j[low].end <= j[i].start が成立する場合は dp[i] += dp[low] を加算します。
   • dp[i] = max(dp[i], dp[i-1]) として、現在のタスクをスキップした場合との最大値を取ります。
6. 最後に dp[n-1] を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
struct Data{
   int s,e,c;
   Data(int x, int y, int z){
      s= x;
      e= y;
      c = z;
   }
};
bool cmp(Data a, Data b){
   return a.e<b.e;
}
class Solution {
   public:
   int jobScheduling(vector<int>& s, vector<int>& e, vector<int>& p){
      vector<Data> j;
      int n = s.size();
      for (int i = 0; i < n; i++) {
         Data temp(s[i], e[i], p[i]);
         j.push_back(temp);
      }
      sort(j.begin(), j.end(), cmp);
      vector<int> dp(n);
      dp[0] = j[0].c;
      for (int i = 1; i < n; i++) {
         int low = 0;
         int high = i - 1;
         while (low < high) {
            int mid = low + (high - low + 1) / 2;
            if (j[mid].e <= j[i].s)
               low = mid;
            else
               high = mid - 1;
         }
         dp[i] = j[i].c;
         if (j[low].e <= j[i].s)
            dp[i] += dp[low];
         dp[i] = max(dp[i], dp[i - 1]);
      }
      return dp[n - 1];
   }
};
main(){
   Solution ob;
   vector<int> startTime = {1,2,3,3}, endTime = {3,4,5,6}, profit =
   {500,100,400,700};
   cout << (ob.jobScheduling(startTime, endTime, profit));
}

入力

{1,2,3,3}, {3,4,5,6}, {500,100,400,700}

出力

1200

計算量について

このアルゴリズムでは、タスクのソートに O(n log n)、各タスクごとの二分探索にも O(log n) かかるため、全体の時間計算量は O(n log n) となります。DP配列の保持には O(n) の空間が必要です。全タスクの組み合わせを総当たりする O(2^n) の手法と比べ、大幅に効率化されている点がこの解法の大きな利点です。