Lợi nhuận tối đa phân công việc trong C++

Cho mảng difficulty, profit của các công việc và mảng worker (khả năng mỗi người). Người làm việc chỉ làm được việc có độ khó ≤ khả năng. Mỗi người làm tối đa 1 việc, 1 việc có thể làm nhiều lần. Tối đa hóa tổng lợi nhuận.

Ví dụ: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7] → 100.

Thuật toán giải quyết (Sắp xếp + Hai con trỏ)

1. Sắp xếp worker tăng dần.
2. Tạo vector cặp (difficulty, profit), sắp xếp theo difficulty.
3. Duyệt worker từ nhỏ đến lớn, duy trì maxVal = lợi nhuận max trong các việc có độ khó ≤ khả năng hiện tại.
4. Cộng dồn maxVal vào kết quả.

Ví dụ minh họa (C++)

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

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

int main() {
    vector<int> difficulty = {2,4,6,8,10};
    vector<int> profit = {10,20,30,40,50};
    vector<int> worker = {4,5,6,7};
    Solution ob;
    cout << ob.maxProfitAssignment(difficulty, profit, worker);
}

Đầu vào

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

Đầu ra

100