Most Profit Assigning Work

MEDIUM

Description

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:

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:

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⁴
1 <= difficulty[i], profit[i], worker[i] <= 10⁵

Approaches

Checkout 3 different approaches to solve Most Profit Assigning Work. Click on different approaches to view the approach and algorithm in detail.

Two Pointers with Sorting

This is the most optimal approach. By sorting both the jobs (by difficulty) and the workers (by ability), we can iterate through them simultaneously using a two-pointer technique to find the maximum profit for each worker in a single pass.

Algorithm

Create a list of Job objects, each with difficulty and profit.
Sort the jobs list by difficulty.
Sort the worker array by ability.
Initialize totalProfit = 0, maxProfitSoFar = 0, and a job pointer jobIndex = 0.
Iterate through each ability in the sorted worker array:
- Use a while loop to advance jobIndex as long as jobs[jobIndex].difficulty <= ability.
- Inside the while loop, update maxProfitSoFar = max(maxProfitSoFar, jobs[jobIndex].profit).
- After the while loop, the current worker can achieve maxProfitSoFar. Add this to totalProfit.
Return totalProfit.

The intuition is that if we process workers in increasing order of their ability, the set of jobs they can do is always a superset of the jobs the previous, less-able worker could do. This monotonicity allows for an efficient single-pass solution. First, we combine difficulty and profit into a list of Job objects. We sort this jobs list based on difficulty and also sort the worker array based on ability. We then use two pointers: one for iterating through the sorted workers (i) and another for the sorted jobs (jobIndex). We also maintain a variable maxProfitSoFar. For each worker, we advance the jobIndex to include all jobs they can perform, updating maxProfitSoFar along the way. The maxProfitSoFar for a worker is then added to the totalProfit. Since the next worker is more capable, we don't need to reset jobIndex or maxProfitSoFar, making the process very efficient.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    class Job {
        int difficulty;
        int profit;
        Job(int difficulty, int profit) {
            this.difficulty = difficulty;
            this.profit = profit;
        }
    }

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        List<Job> jobs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            jobs.add(new Job(difficulty[i], profit[i]));
        }

        Collections.sort(jobs, (a, b) -> a.difficulty - b.difficulty);
        Arrays.sort(worker);

        int totalProfit = 0;
        int maxProfitSoFar = 0;
        int jobIndex = 0;

        for (int ability : worker) {
            while (jobIndex < n && jobs.get(jobIndex).difficulty <= ability) {
                maxProfitSoFar = Math.max(maxProfitSoFar, jobs.get(jobIndex).profit);
                jobIndex++;
            }
            totalProfit += maxProfitSoFar;
        }

        return totalProfit;
    }
}

Complexity Analysis

Time Complexity: O(n log n + m log m). Sorting jobs takes O(n log n), and sorting workers takes O(m log m). The two-pointer traversal takes O(n + m). The sorting steps dominate the complexity.Space Complexity: O(n) to store the list of `Job` objects. The space for sorting depends on the implementation but is typically O(log n) or O(n).

Pros and Cons

Pros:

Most efficient solution in terms of time complexity.
The main logic after sorting is a single linear scan (O(n+m)), which is very fast.

Cons:

Requires extra space (O(n)) to store the job objects.
Modifies the order of the input worker array by sorting it (if sorting in-place).

Code Solutions

Checking out 3 solutions in different languages for Most Profit Assigning Work. Click on different languages to view the code.

class Solution {
public
  int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
    int n = difficulty.length;
    List<int[]> job = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      job.add(new int[]{difficulty[i], profit[i]});
    }
    job.sort(Comparator.comparing(a->a[0]));
    Arrays.sort(worker);
    int res = 0;
    int i = 0, t = 0;
    for (int w : worker) {
      while (i < n && job.get(i)[0] <= w) {
        t = Math.max(t, job.get(i++)[1]);
      }
      res += t;
    }
    return res;
  }
}

Video Solution

Watch the video walkthrough for Most Profit Assigning Work

Algorithms:

Binary SearchSorting

Patterns:

Two PointersGreedy

Data Structures:

Array

Companies:

DoorDash |NetEase |