DSA problem

Most Profit Assigning Work

MediumGreedyPattern: Greedytop600AmazonGoogleMicrosoftBloombergApple

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.

A brute-force pairing tries every (worker, job) combination at cost O(n * m) per query — workable for tiny inputs but quickly stops scaling. We can do much better by recognizing that for each worker, the best job is the highest-profit one whose difficulty is within reach. If we can answer "max profit among all jobs with difficulty <= D" quickly, every worker just looks up their own D.

Sorting unlocks the classic two-pointer pattern. Sort jobs by ascending difficulty and workers by ascending ability. Maintain a job pointer j and a running bestProfit. For each worker in ascending order of ability, advance j while difficulty[j] <= worker.ability, updating bestProfit = max(bestProfit, profit[j]). The current worker contributes bestProfit to the total.

The key correctness observation is monotonicity: as worker ability increases, the set of doable jobs only grows, so bestProfit never decreases. This lets us reuse the same bestProfit across the entire workers loop without resetting. Total time O((n + m) log(n + m)) dominated by the two sorts, and O(n) extra space for the sorted jobs.

Examples

Example 1

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

Output: 100

Explanation: Workers ranked by ability: 4 -> best doable profit is 20 (difficulty 4). 5 -> still 20 (difficulty 6 is too hard). 6 -> 30 (difficulty 6). 7 -> still 30. Total = 20 + 20 + 30 + 30 = 100.

Example 2

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

Output: 0

Explanation: Every job has difficulty >= 47, but the strongest worker has ability 40. No worker can do anything, so total profit = 0.

Example 3

Input: difficulty = [13,37,58], profit = [4,90,96], worker = [34,73,45]

Output: 190

Explanation: Sorted workers [34, 45, 73] map to best profits [4, 90, 96]: worker 34 can do difficulty 13 -> 4, worker 45 can do difficulty 37 -> 90, worker 73 can do difficulty 58 -> 96. Total = 4 + 90 + 96 = 190.

Constraints

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

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

greedyarraytwo-pointerssortingbinary-search

Browse all DSA problems