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 범위의 i에 대해,
- 쌍(난이도[i], 이익[i])을 v에 삽입
v 배열 정렬
maxVal :=0, m :=작업자 배열의 크기 및 j :=0
0 ~ m – 1 범위의 i에 대해
- while j 의 첫 번째 값
- maxVal :=maxVal의 최대값과 v[j]의 두 번째 값
- 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};