Watch 10 video solutions for Most Profit Assigning Work, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by codestorywithMIK has 10,717 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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, andworker[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.
$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.lengthn == profit.lengthm == worker.length1 <= n, m <= 1041 <= difficulty[i], profit[i], worker[i] <= 105Problem Overview: You get two arrays describing jobs: difficulty[i] and profit[i]. Each worker has a skill level and can complete any job whose difficulty is less than or equal to their skill. A job can be assigned multiple times. The goal is to assign each worker the most profitable job they can handle and return the total profit.
Approach 1: Sorting and Greedy Matching (O((n + m) log n) time, O(1) extra space)
This approach combines sorting with a greedy sweep. Pair each job's difficulty and profit, then sort jobs by difficulty. Sort the worker array as well. Walk through workers from lowest to highest skill while advancing a pointer through the sorted jobs whose difficulty is within the worker's capability.
While scanning jobs, track the maximum profit seen so far. For each worker, update the pointer for all jobs they can perform and assign the best profit encountered. The greedy insight: if a worker can do harder jobs, they automatically have access to all easier jobs, so keeping a running maximum profit guarantees the optimal choice without re-checking previous jobs.
This method avoids nested loops. Each job and worker is processed once after sorting, making it efficient for large inputs.
Approach 2: Efficient Profit Calculation with One Pass (O(n log n + m) time, O(n) space)
Sort jobs by difficulty and build a prefix array where each position stores the maximum profit achievable up to that difficulty. For example, if a harder job has lower profit than an easier one, the prefix keeps the better value. This preprocessing step converts the job list into a monotonic profit lookup.
Next, process workers. If workers are sorted, you can scan the job list once using a moving pointer and assign profits in a single pass. Alternatively, you can perform binary search to find the rightmost job whose difficulty is less than or equal to the worker's skill, then read the prefix maximum profit.
The key idea is decoupling job difficulty from profit selection. By precomputing the best achievable profit up to each difficulty level, worker assignment becomes a fast lookup instead of repeatedly comparing all jobs.
Recommended for interviews: The sorting + greedy sweep is the most commonly expected solution. It clearly demonstrates understanding of greedy optimization, pointer scanning, and efficient iteration over sorted data. The prefix-max variant is also strong when discussing alternative optimizations or when binary search fits naturally into the design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Greedy Matching | O((n + m) log n) | O(1) | General case; easiest to implement and commonly expected in interviews |
| Prefix Max Profit + One Pass | O(n log n + m) | O(n) | Useful when building fast profit lookups or combining with binary search |