Leetcode 826. Most Profit Assigning Work

Problem Explanation

The given problem involves assigning jobs to workers depending on their capabilities to maximize profit. We are given three lists:

• The first list "difficulty" denotes the difficulty level of each job.
• The second list "profit" denotes the respective profit we get when each job is completed.
• The third list "worker" denotes the ability level of workers.

A worker can only complete a job if the job difficulty is less than or equal to his ability.

Our task is to maximize the total profit by smartly assigning jobs to the workers. If a worker is not capable of doing any job, they don't earn any profit. Each worker can only do one job, but a job can be done by multiple workers.

The approach to solve the problem is to sort jobs by their difficulty, and using a pointer to keep track of which job the current worker can do in the sorted jobs list. If a worker can do a job, we compare the profit with maxProfit, which represents the maximum profit a worker can achieve previously, and update maxProfit if the current profit is larger. Since jobs are sorted by their difficulty, the profit a worker can get is either the profit of the current job or maxProfit.

Approach

Consider the example:

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

The steps involved are:

1. We create pairs of jobs (difficulty, profit) and sort the pairs.
2. We also sort the worker list for easier comparison.
3. We initialize two pointers, i to keep track of the current job and maxProfit to hold the maximum profit of the job we have seen so far.
4. For every worker, we keep checking jobs until we find a job that has a difficulty level the worker cannot handle. During this, we also update maxProfit with any higher profit than maxProfit.
5. Once we reach a job the worker can't handle, we add the current maxProfit to the total answer since it's the maximum profit a worker can achieve.
6. Repeat steps 4 and 5 for every worker.

Python Solution

1
2python
3class Solution:
4    def maxProfitAssignment(self, difficulty, profit, worker):
5        jobs = sorted(zip(difficulty, profit))
6        worker.sort()
7  
8        i, ans, max_profit = 0, 0, 0
9        for w in worker:
10            while i < len(jobs) and w >= jobs[i][0]:
11                max_profit = max(max_profit, jobs[i][1])
12                i += 1
13            ans += max_profit
14        return ans

We create a list of pairs with difficulty and profit of jobs. Then, we sort both jobs and worker lists and initialize the current index i to 0, the total profit ans to 0, and maximum profit so far max_profit to 0. Then, for each worker, we get the current job and update our variables. We keep adding the maximum profit to our answer.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit,
6                          vector<int>& worker) {
7    int ans = 0;
8    vector<pair<int, int>> jobs;
9
10    for (int i = 0; i < difficulty.size(); ++i)
11      jobs.emplace_back(difficulty[i], profit[i]);
12
13    sort(begin(jobs), end(jobs));
14    sort(begin(worker), end(worker));
15
16    int i = 0;
17    int maxProfit = 0;
18
19    for (const int w : worker) {
20      for (; i < jobs.size() && w >= jobs[i].first; ++i)
21        maxProfit = max(maxProfit, jobs[i].second);
22      ans += maxProfit;
23    }
24    return ans;
25  }
26};

The C++ solution is similar to the Python solution but more verbose.

Java Solution

1
2java
3class Solution {
4    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
5        int N = difficulty.length;
6        int[][] jobs = new int[N][2];
7        for (int i = 0; i < N; ++i) {
8            jobs[i] = new int[]{difficulty[i], profit[i]};
9        }
10        
11        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
12        Arrays.sort(worker);
13        int i = 0, best = 0, totalProfit = 0;
14        for (int ability : worker) {
15            while (i < N && ability >= jobs[i][0]) {
16                best = Math.max(best, jobs[i++][1]);
17            }
18            totalProfit += best;
19        }
20        return totalProfit;
21    }
22}

Java solution is structured the same way as the other solutions, using a two-dimensional array to hold 'jobs' as pairs of difficulty and profit.

C# Solution

1
2cs
3public class Solution {
4    public int MaxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
5        var jobs = new List<(int, int)>();
6        for (int i = 0; i < difficulty.Length; i++) {
7            jobs.Add((difficulty[i], profit[i]));
8        }
9        jobs = jobs.OrderBy(job => job.Item1).ToList();
10        var sortedWorkers = worker.OrderBy(w => w).ToList();
11
12        int i = 0;
13        int best = 0;
14        int totalProfit = 0;
15        foreach (var ability in sortedWorkers) {
16            while (i < jobs.Count && ability >= jobs[i].Item1) {
17                best = Math.Max(best, jobs[i].Item2);
18                i++;
19            }
20            totalProfit += best;
21        }
22        return totalProfit;
23    }
24}

C# solution uses a list of tuples to hold 'jobs' which are pairs of difficulty and profit.

Javascript Solution

1
2Javascript
3var maxProfitAssignment = function(difficulty, profit, worker) {
4    let jobs = [], i = 0, res = 0, max = 0;
5    for(let j = 0; j < difficulty.length; j++) jobs.push([difficulty[j], profit[j]]);
6    jobs.sort((a,b) => a[0] - b[0]);
7    worker.sort((a,b) => a - b);
8    for(let w of worker) {
9        while(i < jobs.length && jobs[i][0] <= w) max = Math.max(max, jobs[i++][1]);
10        res += max;
11    }
12    return res;
13};

Each solution follows the same approach in assigning the maximum profitable job a worker can finish, we just iteratively ensure workers have the best potential profit using variable maxProfit or best or max depending on the language used.The problem statement is based on the principle of greedy algorithm. We first sort the job difficulties and worker abilities in ascending order and then assign the maximum possible profit a worker can gain from the available jobs.

The Python, C++, Java, and C# implementations are straightforward and follow the same approach. They first pair up the job difficulties with their corresponding profits and then sort this pair along with the worker's ability.

The JavaScript solution does the same except it also sorts the job difficulties.

An important concept used in all these solutions is that we are adjusting the maximum profit maxProfit or best or max every time we find a job that a worker can do and has a higher profit than the current maxProfit. Once we find a job that a worker can't do, we know the job before it provides the maximum profit the worker could get, so we add maxProfit to our total profit.

This solution is quite efficient because we only need to go over the worker and jobs lists once, which gives us a time complexity of O(n log n) mainly due to the sorting operations.

Tests

You can test your solution with the following test cases:

1. difficulty = [68,35,52,47,86], profit = [67,17,1,81,3], worker = [92,10,85,84,82] Expected output: 324

2. difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25] Expected output: 0

3. difficulty = [5,5,5], profit = [1,2,3], worker = [3,3,3] Expected output: 0

4. difficulty = [49,88,60,62,77,55,87], profit = [92,65,36,85,79,85,16], worker = [68,85,16,8,13,36,38] Expected output: 455

It's also a good idea to test edge cases, such as having an empty difficulty or profit list, or having a single job and worker. Make sure your solution correctly handles these cases.