Most Profit Assigning Work Problem


Description

LeetCode Problem 826.

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 i^th job, and
  • worker[j] is the ability of j^th worker (i.e., the j^th 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.

Example 1:

1
2
3
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

Example 2:

1
2
Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0

Constraints:

  • n == difficulty.length
  • n == profit.length
  • m == worker.length
  • 1 <= n, m <= 10^4
  • 1 <= difficulty[i], profit[i], worker[i] <= 10^5


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        vector<pair<int,int>> vc;
        for (int i = 0; i < difficulty.size(); i++) 
            vc.push_back(make_pair(difficulty[i], profit[i]));   
        sort(vc.begin(), vc.end());
        for (int i = 1; i < vc.size(); i++) 
            vc[i].second = max(vc[i].second, vc[i - 1].second);
         
        sort(worker.begin(), worker.end());
        int  x = 0, ans = 0;
        for (int i = 0; i < worker.size(); i++) {
            while (vc[x].first <= worker[i] && vc.size() > x) {
                x++;
            }
            ans += x == 0 ? 0 : vc[x - 1].second;
        }
        return ans;
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Push Dominoes Problem

LeetCode 838. There are n dominoes in a line, and...