C++ में सर्वाधिक लाभ असाइनमेंट कार्य

मान लीजिए कि हमारे पास नौकरी की कठिनाई है [i] और यह सरणी ith नौकरी की कठिनाई को इंगित करती है, और लाभ [i] ith नौकरी का लाभ है। अब विचार करें कि हमारे पास कुछ कार्यकर्ता हैं। कार्यकर्ता [i] ith कार्यकर्ता की क्षमता है, इसका मतलब है कि यह कार्यकर्ता केवल अधिकांश कार्यकर्ता [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 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• उत्तर :=0 और n :=लाभ सरणी का आकार
• कार्यकर्ता सरणी को क्रमबद्ध करें
• v नामक जोड़ियों की सूची बनाएं
• मैं के लिए 0 से n - 1 की सीमा में,
  • जोड़ी (कठिनाई[i], लाभ[i]) को v में डालें
• v सरणी को क्रमबद्ध करें
• maxVal :=0, m :=कार्यकर्ता सरणी का आकार और j :=0
• मैं के लिए 0 से मी - 1 की सीमा में
  • जबकि j
  • maxVal :=maxVal का अधिकतम और v[j] का दूसरा मान
  • j को 1 से बढ़ाएं
• उत्तर:=उत्तर + मैक्सवैल

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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