[LeetCode] 826. Most Profit Assigning Work

https://leetcode.com/problems/most-profit-assigning-work/description/

leetcode - Most Profit Assigning Work

문제 유형 : 정렬, 그리디, 이진탐색

문제 난이도 : Medium

 

문제

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.

 

n개의 일과 m명의 노동자가 있다.

difficulty, profit, worker배열을 받는다.

difficulty[i]와 profit[i]는 i번째 일의 난이도와 수익이다.

worker[j]는 j번째 노동자의 능력이다. j번째 노동자는 worker[j]가 difficulty[i]보다 크거나 같아야 i번째 일을 할 수 있다.

 

각 노동자들은 최대 한 개의 일을 할당받는다.

하나의 일은 여러 노동자가 같이 맡아도 된다.

 

최대 이익을 구하시오.

 

풀이

문제의 핵심은 난이도가 높다고 수익이 많이 나오는 것이 아니라는 것에 명심하는 것이다.

works배열에 {난이도, 수익}의 형태로 저장시킨다.

 

works배열을 난이도기준 오름차순정렬시킨다.

works배열을 순회하면서 각 난이도별로 얻을 수 있는 최대 수익으로 업데이트시킨다.

 

이제, 각 노동자 배열을 순회하면서 각자 최대 얻을 수 있는 수익을 누적시킨다.

이진 탐색을 통해서 빠르게 얻을 수 있다.

마지막으로, 누적된 값을 반환한다.

 

코드

C++

class Solution {
public:
    int getMax(int ability, vector<vector<int>>& works) {
        int left = 0, right = works.size() - 1;
        int res = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (works[mid][0] <= ability) {
                res = (res, works[mid][1]);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return res;
    }

    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int n = profit.size();
        int m = worker.size();
        int ans = 0;
        vector<vector<int>> works;
        
        for (int i = 0; i < n; i++) {
            works.push_back({difficulty[i], profit[i]});
        }

        sort(works.begin(), works.end());

        for (int i = 1; i < works.size(); i++) {
            works[i][1] = max(works[i][1], works[i-1][1]);
        }

        for (int i = 0; i < m; i++) {
            ans += getMax(worker[i], works);
        }

        return ans;
    }
};