[Leetcode 826번 문제] 826. Most Profit Assigning Work

문제 상황

You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:

• difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and
• worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).

Every worker can be assigned at most one job, but one job can be completed multiple times.

• For example, if three workers attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, their profit is $0.

Return the maximum profit we can achieve after assigning the workers to the jobs.

Difficulty 내에서 얻을 수있는 최대의 profit을 구하는 문제이다 일에 대한 difficulty가 있고 그에대한 profit이 있음

그리고 일 수행 능력에 대한 worker 배열이 있음

여기서 모든 worker들에게 일을 시킨다고 하였을 때 얻을 수 있는 최대 이익을 리턴하는 문제.

입력

• n == difficulty.length
• n == profit.length
• m == worker.length
• 1 <= n, m <= 104
• 1 <= difficulty[i], profit[i], worker[i] <= 105

출력

worker들에게 최대로 일을 시켰을때 얻을 수 있는 최대 이익

과정

작은 하나의 worker 들에게 필요한 값은 - 나보다 같거나 작은 난이도에서 최대의 Profit을 내는 작업일 것이다.

그럼 첫 worker는 이전 worker와 이 과정의 일부를 공유할 수 있다. 직렬화 할 수 있다.

알고리즘 개요도

알고리즘

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        vector<pair<int, int>> difficultyProfit {};
        for (int i = 0; i < profit.size(); i++)
        {
            difficultyProfit.push_back({difficulty[i], profit[i]});
        }
        sort(difficultyProfit.begin(), difficultyProfit.end());
        sort(worker.begin(), worker.end());
        int pdIndex = 0;
        int maxValue = 0;
        int ans = 0;
        for (int index = 0; index < worker.size(); index++ )
        {
            while (pdIndex < difficultyProfit.size() && worker[index] >= difficultyProfit[pdIndex].first)
            {
                maxValue = max(maxValue, difficultyProfit[pdIndex].second);
                pdIndex++;
            }
            ans += maxValue;
        }
        return ans;
    }
};