งานมอบหมายผลกำไรสูงสุดใน C++

สมมติว่าเรามีปัญหากับงาน[i] และอาร์เรย์นี้ระบุความยากของงาน ith และ profit[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 ทั้งหมด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ans :=0 และ n :=ขนาดของอาร์เรย์กำไร
• จัดเรียงอาร์เรย์ผู้ปฏิบัติงาน
• ทำรายการคู่ที่เรียกว่า v
• สำหรับ i ในช่วง 0 ถึง n – 1,
  • ใส่คู่ (ความยาก[i], profit[i]) ลงใน v
• เรียงลำดับ v อาร์เรย์
• maxVal :=0, m :=ขนาดของอาร์เรย์คนงานและ j :=0
• สำหรับ i ในช่วง 0 ถึง m – 1
  • ในขณะที่ 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};

ผลลัพธ์

100