Scale Engineer

Most Profit Assigning Work

Med
#0780Time: 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: 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).2 companies
Patterns
Two PointersGreedy
Algorithms
Binary SearchSorting
Data structures
Array
Companies
DoorDashNetEase

Prompt

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.

 

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 <= 104
  • 1 <= difficulty[i], profit[i], worker[i] <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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).

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem