826 Most Profit Assigning Work

826. Most Profit Assigning Work

1. Question

We have jobs:difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

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

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

What is the most profit we can make?

Example 1:

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

Output: 
100 

Explanation: W
orkers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.

Notes:

• 1 <= difficulty.length = profit.length <= 10000

• 1 <= worker.length <= 10000

• difficulty[i], profit[i], worker[i]are in range[1, 10^5]

2. Implementation

(1) Two Pointer

思路: 其实最核心的问题就是，对于每个worker，在他能力level以内，哪个级别获得profit最大？所以我们首先将diffulty和对应的profit联系起来(这里的解法里用jobs这个2d数组)，然后将jobs按照difficulty level从小到大排序。然后对于每个worker，我们就从他的能力level开始往下找出，他能力范围内可以获得的最大profit。这里可以做的一个优化是，对于相同的level来说，能获得的最大的profit是确定的，所以我们可以先对worker数组排序，这样我们就可以不用每个worker都从他的能力到最低level找出最大，避免重复寻找相同能力的worker

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = profit.length;

        int[][] jobs = new int[n][2];

        for (int i = 0; i < n; i++) {
            jobs[i][0] = difficulty[i];
            jobs[i][1] = profit[i];
        }

        Arrays.sort(jobs, (a, b)->(a[0] - b[0]));
        Arrays.sort(worker);

        int res = 0;
        int i = 0;
        int maxProfit = 0;

        for (int ability : worker) {            
            while (i < n && ability >= jobs[i][0]) {
                maxProfit = Math.max(maxProfit, jobs[i][1]);
                ++i;
            }
            res += maxProfit;
        }
        return res;
    }
}

3. Time & Space Complexity

Two Pointer: 时间复杂度O(nlogn), 空间复杂度O(n)