C ++中的大多数利润分配工作

假设我们有工作难度[i]，此数组表示第i个工作的难度，而利润[i]是第i个工作的利润。现在考虑我们有一些工人。worker [i]是第i个工人的能力，这意味着该工人最多只能完成困难的工作[i]。每个工人最多只能完成一项工作，但是一项工作可以完成多次。我们必须找到最大的利润是什么？

例如，如果输入的难度为[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的范围内

• 将对（difficulty [i]，profit [i]）插入v

• 对v数组排序

• maxVal：= 0，m：= worker数组的大小，j：= 0

• 当我的范围是0到m – 1

• maxVal：= maxVal的最大值和v [j]的第二个值

• 将j增加1

• 而j <n和v [j] <= worker [i]的第一个值

• ans：= ans + maxVal

• 返回ans

让我们看下面的实现以更好地理解-

示例

#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