Most Profit Assigning Work ใน C++: กำหนดงานให้คนทำงานเพื่อกำไรสูงสุด

โจทย์

มีงาน n งาน: difficulty[i], profit[i] มีคนงาน m คน: worker[i] = ความสามารถ (ทำงานได้ที่ difficulty ≤ worker[i]) คนงานแต่ละคนทำได้ ≤ 1 งาน งานทำซ้ำได้ หากำไรรวมสูงสุด

ตัวอย่าง: diff=[2,4,6,8,10], profit=[10,20,30,40,50], worker=[4,5,6,7] → 100 (มอบงาน diff 4,4,6,6 → profit 20+20+30+30)

แนวคิด: เรียงคนงาน + Two Pointers + Max Prefix Profit

เรียงงานตาม difficulty, เรียงคนงานตามความสามารถ เดิน pointer งานพร้อมกับคนงาน เก็บ max profit ที่ difficulty ≤ worker[i]

ขั้นตอน

1. สร้าง vector pairs jobs = {(diff, profit)} เรียงตาม diff
2. เรียง worker
3. j = 0, maxProfit = 0, ans = 0
4. ลูปคนงาน i = 0 ถึง m-1:
   • while j < n && jobs[j].first <= worker[i]:
     • maxProfit = max(maxProfit, jobs[j].second)
     • j++
   • ans += maxProfit
5. คืน ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int n = difficulty.size();
        vector<pair<int,int>> jobs(n);
        for (int i = 0; i < n; i++) jobs[i] = {difficulty[i], profit[i]};
        sort(jobs.begin(), jobs.end());
        sort(worker.begin(), worker.end());
        
        int ans = 0, maxProfit = 0, j = 0;
        for (int w : worker) {
            while (j < n && jobs[j].first <= w) {
                maxProfit = max(maxProfit, jobs[j].second);
                j++;
            }
            ans += maxProfit;
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> diff = {2,4,6,8,10};
    vector<int> prof = {10,20,30,40,50};
    vector<int> work = {4,5,6,7};
    cout << ob.maxProfitAssignment(diff, prof, work); // 100
    return 0;
}

อินพุต / เอาต์พุต

Input: [2,4,6,8,10] [10,20,30,40,50] [4,5,6,7]

Output: 100

ความซับซ้อน

• Time: O(n log n + m log m) - เรียงลำดับ
• Space: O(n)