সি++-এ সর্বাধিক লাভ বরাদ্দের কাজ

ধরুন আমাদের কাজের অসুবিধা[i] এবং এই অ্যারেটি ith কাজের অসুবিধা নির্দেশ করে এবং লাভ[i] হল ith কাজের লাভ। এখন বিবেচনা করুন আমাদের কিছু কর্মী আছে। worker[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 এর মধ্যে,
- v এ জোড়া (কঠিনতা[i], লাভ[i]) সন্নিবেশ করান
v অ্যারে সাজান
maxVal :=0, m :=কর্মী অ্যারের আকার এবং j :=0
আমি 0 থেকে m – 1
- যখন j এর প্রথম মান
- maxVal :=maxVal এর সর্বোচ্চ এবং v[j] এর দ্বিতীয় মান।
- j 1 দ্বারা বাড়ান
উত্তর :=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};