C++でのジョブスケジューリングの最大利益

n個の異なるタスクがあり、すべてのタスクがstartTime[i]からendTime[i]まで実行されるようにスケジュールされていると仮定します。そのタスクでは、利益[i]を得ることができます。 startTime、endTime、および利益のリストがわかっているので、時間範囲が重複するサブセットに2つのタスクがないように、取得できる最大の利益を見つける必要があります。時間Xで終了するタスクを選択すると、時間Xで開始する別のタスクを開始できます。

したがって、入力がstartTime =[1,2,3,3]の場合、endTime=[3,4,5,6]利益=[500,100,400,700]

その場合、出力は1200

これを解決するには、次の手順に従います-

• 開始値、終了値、およびコスト値を使用して1つのデータを定義します

• データjの1つの配列を作成します

• n：=sのサイズ

• 初期化i：=0の場合、i

  • 1つのデータtemp（s [i]、e [i]、p [i]）

    を作成します

  • jの最後にtempを挿入

• 終了時間に基づいて配列jを並べ替えます

• サイズnの配列dpを定義します

• dp [0]：=j [0] .cost

• 初期化i：=1の場合、i

  • temp：=0、low：=0、high：=i-1

  • 低<高、実行-

    • 中：=低+（高-低+ 1）/ 2

    • j [mid] .end <=j [i] .startの場合、-

      • 低：=中

    • それ以外の場合

      • 高：=中-1

    • dp [i]：=j [i] .cost

    • j [low] .end <=j [i] .startの場合、-

      • dp [i]：=dp [i] + dp [low]

  • dp [i]：=dp[i]とdp[i-1]の最大値

• dp [n-1]

  を返します

理解を深めるために、次の実装を見てみましょう-

例

#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 temp = 0;
         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