C++でのほとんどの利益配分作業

ジョブの難易度[i]があり、この配列がi番目のジョブの難易度を示し、profit[i]がi番目のジョブの利益であるとします。ここで、何人かの労働者がいると考えてください。 worker [i]はi番目のワーカーの能力です。つまり、このワーカーはほとんどのworker[i]でしか仕事を完了できません。すべてのワーカーは最大で1つのジョブを実行できますが、1つのジョブは複数回完了することができます。私たちが稼ぐことができる最大の利益は何であるかを見つけなければなりませんか？

たとえば、入力が難易度=[2,4,6,8,10]、利益=[10,20,30,40,50]、ワーカー=[4,5,6,7]のような場合、出力は100になります。したがって、労働者には仕事の難易度[4,4,6,6]と、得られた利益[20,20,30,30]、つまり合計100を割り当てることができます。

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

• ans：=0およびn：=利益配列のサイズ
• ワーカー配列を並べ替える
• vと呼ばれるペアのリストを作成します
• 0からn–1の範囲のiの場合
  • ペア（difficulty [i]、profit [i]）をvに挿入します
• v配列を並べ替える
• maxVal：=0、m：=ワーカー配列のサイズ、j：=0
• 0からm–1の範囲のiの場合
  • 一方、j
  • maxVal：=maxValの最大値とv[j]の2番目の値
  • jを1増やします
• ans：=ans + maxVal

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
      int ans = 0;
      sort(worker.begin(), worker.end());
      vector < pair <int, int> > v;
      int n = profit.size(); // Number of jobs
      for(int i = 0; i < n; i++){
         v.push_back({difficulty[i], profit[i]});
      }
      sort(v.begin(), v.end());
      int maxVal = 0;
      int m = worker.size(); // Number of workers
      int j = 0;
      for(int i = 0; i < m; i++){
         while(j < n && v[j].first <= worker[i]){
            maxVal = max(maxVal, v[j].second);
            j++;
         }
         ans += maxVal;
      }
      return ans;
   }
};
int main() {
   Solution ob1;
   vector<int> difficulty{2,4,6,8,10};
   vector<int> profit{10,20,30,40,50};
   vector<int> worker{4,5,6,7};
   cout << ob1.maxProfitAssignment(difficulty, profit, worker) << endl;
   return 0;
}

入力

[2,4,6,8,10]
[10,20,30,40,50]
[4,5,6,7]
vector<int> difficulty{2,4,6,8,10};
vector<int> profit{10,20,30,40,50};
vector<int> worker{4,5,6,7};

出力

100