Most Profit Assigning Work solution and explanation
Google
9 more videos on this problem
Most Profit Assigning Work | Multiple Approaches | With Intuition | Leetcode 826 | codestorywithMIKcodestorywithMIK · 37:28 · 11K views
826. Most Profit Assigning Work | 5 Approaches | Greedy | Binary S | Priority Queue | 2 Pointer | DPAryan Mittal · 26:18 · 6K views
826. Most Profit Assigning Work | count sort | max array | leetcode daily challenge | DSA | HindiShashCode · 26:47 · 2K views
✅Most Profit Assigning Work - LeetCode 826 - Dynamic Programming - Explained in Detail -Step by StepLeet Logics · 9:14 · 2K views
LeetCode Chief - 826. Most Profit Assigning WorkArtem Kudria · 12:32 · 1K views
Most Profit Assigning Work | Leetcode 826Ayushi Sharma · 23:50 · 1K views
LeetCode 826 - Most Profit Assigning Work - JavaAlpha-Code · 12:12 · 454 views
Most Profit Assigning Work - Leetcode 826 - JavaCode With K5KC · 11:21 · 160 views
[June 18, 2024, LeetCode daily] 826. Most Profit Assigning Work - Python, solution explainedhornclause · 3:13 · 64 views
826. Most Profit Assigning Work | INTUITIVE | MEMOIZATION | Linear Time | LeetCode 826Amit Dhyani · 29:52 · 61 views
The problem
You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:
difficulty[i]andprofit[i]are the difficulty and the profit of theithjob, andworker[j]is the ability ofjthworker (i.e., thejthworker can only complete a job with difficulty at mostworker[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.lengthn == profit.lengthm == worker.length1 <= n, m <= 1041 <= difficulty[i], profit[i], worker[i] <= 105
Approach overview
Problem 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 1: Approach 1: Sorting and Greedy Matching
In this approach, we sort both jobs by difficulty and workers by their ability. We then iterate over each worker and find the highest profit job they can perform using a greedy approach.
First, we pair each job's difficulty with its profit and then sort these pairs by difficulty. We also sort the worker array. Next, for each worker, we iterate through the sorted job list and keep track of the maximum profit the worker can obtain, given that their ability must be greater than or equal to the job's difficulty. This ensures that each worker is assigned the most profitable job they can perform, thus maximizing the total profit.
def maxProfitAssignment(difficulty, profit, worker):
jobs = sorted(zip(difficulty, profit))
worker.sort()
maxProfit = 0
best = 0
j = 0
n = len(jobs)
for ability in worker:
while j < n and ability >= jobs[j][0]:
best = max(best, jobs[j][1])
j += 1
maxProfit += best
return maxProfit
print(maxProfitAssignment([2, 4, 6, 8, 10], [10, 20, 30, 40, 50], [4, 5, 6, 7]))import java.util.Arrays;
public class MaxProfitAssignment {
public static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
int n = difficulty.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 maxProfit = 0, best = 0, j = 0;
for (int ability : worker) {
while (j < n && ability >= jobs[j][0]) {
best = Math.max(best, jobs[j][1]);
j++;
}
maxProfit += best;
}
return maxProfit;
}
public static void main(String[] args) {
int[] difficulty = {2, 4, 6, 8, 10};
int[] profit = {10, 20, 30, 40, 50};
int[] worker = {4, 5, 6, 7};
System.out.println("Max Profit: " + maxProfitAssignment(difficulty, profit, worker));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
vector<pair<int, int>> jobs;
for (size_t i = 0; i < difficulty.size(); ++i) {
jobs.emplace_back(difficulty[i], profit[i]);
}
sort(jobs.begin(), jobs.end());
sort(worker.begin(), worker.end());
int maxProfit = 0, best = 0, j = 0;
for (auto& ability : worker) {
while (j < jobs.size() && ability >= jobs[j].first) {
best = max(best, jobs[j].second);
++j;
}
maxProfit += best;
}
return maxProfit;
}
int main() {
vector<int> difficulty = {2, 4, 6, 8, 10};
vector<int> profit = {10, 20, 30, 40, 50};
vector<int> worker = {4, 5, 6, 7};
int maxProfit = maxProfitAssignment(difficulty, profit, worker);
cout << "Max Profit: " << maxProfit << endl;
return 0;
}function maxProfitAssignment(difficulty, profit, worker) {
const jobs = difficulty.map((d, i) => [d, profit[i]]);
jobs.sort((a, b) => a[0] - b[0]);
worker.sort((a, b) => a - b);
let maxProfit = 0, best = 0, j = 0;
for (let ability of worker) {
while (j < jobs.length && ability >= jobs[j][0]) {
best = Math.max(best, jobs[j][1]);
j++;
}
maxProfit += best;
}
return maxProfit;
}
console.log(maxProfitAssignment([2, 4, 6, 8, 10], [10, 20, 30, 40, 50], [4, 5, 6, 7]));#include <stdio.h>
#include <stdlib.h>
int compareJobs(const void *a, const void *b) {
return ((int *)a)[0] - ((int *)b)[0];
}
int compareWorkers(const void *a, const void *b) {
return (*(int *)a) - (*(int *)b);
}
int maxProfitAssignment(int* difficulty, int difficultySize, int* profit, int profitSize, int* worker, int workerSize) {
int jobs[difficultySize][2];
for (int i = 0; i < difficultySize; i++) {
jobs[i][0] = difficulty[i];
jobs[i][1] = profit[i];
}
qsort(jobs, difficultySize, sizeof(jobs[0]), compareJobs);
qsort(worker, workerSize, sizeof(int), compareWorkers);
int maxProfit = 0, best = 0, j = 0;
for (int i = 0; i < workerSize; i++) {
while (j < difficultySize && worker[i] >= jobs[j][0]) {
best = (best > jobs[j][1]) ? best : jobs[j][1];
j++;
}
maxProfit += best;
}
return maxProfit;
}
int main() {
int difficulty[] = {2, 4, 6, 8, 10};
int profit[] = {10, 20, 30, 40, 50};
int worker[] = {4, 5, 6, 7};
int maxProfit = maxProfitAssignment(difficulty, 5, profit, 5, worker, 4);
printf("Max Profit: %d\n", maxProfit);
return 0;
}using System;
using System.Linq;
public class Solution {
public int MaxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
var jobs = difficulty.Zip(profit, (d, p) => new { Difficulty = d, Profit = p })
.OrderBy(j => j.Difficulty)
.ToArray();
Array.Sort(worker);
int maxProfit = 0, best = 0, j = 0;
foreach (int ability in worker) {
while (j < jobs.Length && ability >= jobs[j].Difficulty) {
best = Math.Max(best, jobs[j].Profit);
j++;
}
maxProfit += best;
}
return maxProfit;
}
public static void Main() {
var solution = new Solution();
Console.WriteLine(solution.MaxProfitAssignment(new int[] {2, 4, 6, 8, 10}, new int[] {10, 20, 30, 40, 50}, new int[] {4, 5, 6, 7}));
}
}Python's sort and zip functions are used to prepare data. The main logic iterates over sorted workers and, using a pointer for jobs, it keeps track of the maximum profit any worker can achieve.
Time Complexity: O(n log n + m log m)
Space Complexity: O(n)
Approach 2: Approach 2: Efficient Profit Calculation with One Pass
This approach improves efficiency by preparing the job list in advance for profit maximization, and processes each worker in one pass. The basic idea is to preprocess the jobs to track the maximum profit obtainable up to each difficulty level. We create a running maximum profit and apply this to each worker based on their ability directly.
First, jobs are paired and sorted by difficulty; then, as we iterate through them, we constantly update the maximum profit obtainable up to each job's difficulty. When assessing workers, we simply apply their ability to this precomputed list to find the applicable maximum profit, ensuring minimal lookups and passing through the sorted jobs just once.
def maxProfitAssignment(difficulty, profit, worker):
jobs = sorted(zip(difficulty, profit))
worker.sort()
maxProfit = 0
best = 0
j = 0
n = len(jobs)
for i in range(n):
best = max(best, jobs[i][1])
jobs[i] = (jobs[i][0], best) # Keep track of best profit at each difficulty
for ability in worker:
while j < n and ability >= jobs[j][0]:
j += 1
if j > 0:
maxProfit += jobs[j - 1][1]
return maxProfit
print(maxProfitAssignment([2, 4, 6, 8, 10], [10, 20, 30, 40, 50], [4, 5, 6, 7]))import java.util.Arrays;
public class MaxProfitAssignment {
public static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
int n = difficulty.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) -> Integer.compare(a[0], b[0]));
Arrays.sort(worker);
int maxProfit = 0, best = 0, j = 0;
for (int i = 0; i < n; i++) {
if (jobs[i][1] > best) {
best = jobs[i][1];
}
jobs[i][1] = best;
}
for (int ability : worker) {
while (j < n && ability >= jobs[j][0]) {
j++;
}
if (j > 0) {
maxProfit += jobs[j - 1][1];
}
}
return maxProfit;
}
public static void main(String[] args) {
int[] difficulty = {2, 4, 6, 8, 10};
int[] profit = {10, 20, 30, 40, 50};
int[] worker = {4, 5, 6, 7};
System.out.println("Max Profit: " + maxProfitAssignment(difficulty, profit, worker));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
vector<pair<int, int>> jobs;
for (size_t i = 0; i < difficulty.size(); ++i) {
jobs.emplace_back(difficulty[i], profit[i]);
}
sort(jobs.begin(), jobs.end());
sort(worker.begin(), worker.end());
int maxProfit = 0, best = 0, j = 0;
for (auto& job : jobs) {
best = max(best, job.second);
job.second = best; // Update the job profit to maximum up to this difficulty
}
for (auto& ability : worker) {
while (j < jobs.size() && ability >= jobs[j].first) {
++j;
}
if (j > 0) {
maxProfit += jobs[j - 1].second;
}
}
return maxProfit;
}
int main() {
vector<int> difficulty = {2, 4, 6, 8, 10};
vector<int> profit = {10, 20, 30, 40, 50};
vector<int> worker = {4, 5, 6, 7};
int maxProfit = maxProfitAssignment(difficulty, profit, worker);
cout << "Max Profit: " << maxProfit << endl;
return 0;
}function maxProfitAssignment(difficulty, profit, worker) {
const jobs = difficulty.map((d, i) => [d, profit[i]]);
jobs.sort((a, b) => a[0] - b[0]);
worker.sort((a, b) => a - b);
let maxProfit = 0;
let best = 0;
let j = 0;
const n = jobs.length;
jobs.forEach(job => {
best = Math.max(best, job[1]);
job[1] = best; // Precompute max profit for every difficulty level
});
worker.forEach(ability => {
while (j < n && ability >= jobs[j][0]) {
j++;
}
if (j > 0) {
maxProfit += jobs[j - 1][1];
}
});
return maxProfit;
}
console.log(maxProfitAssignment([2, 4, 6, 8, 10], [10, 20, 30, 40, 50], [4, 5, 6, 7]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return ((int *)a)[0] - ((int *)b)[0];
}
int maxProfitAssignment(int* difficulty, int difficultySize, int* profit, int profitSize, int* worker, int workerSize) {
int jobs[difficultySize][2];
for (int i = 0; i < difficultySize; i++) {
jobs[i][0] = difficulty[i];
jobs[i][1] = profit[i];
}
qsort(jobs, difficultySize, sizeof(jobs[0]), compare);
qsort(worker, workerSize, sizeof(int), compare);
int maxProfit = 0, best = 0, j = 0;
for (int i = 0; i < difficultySize; i++) {
if (jobs[i][1] > best) {
best = jobs[i][1];
}
jobs[i][1] = best; // Store max profit up to this difficulty
}
for (int i = 0, j = 0; i < workerSize; i++) {
while (j < difficultySize && worker[i] >= jobs[j][0]) {
j++;
}
if (j > 0) {
maxProfit += jobs[j - 1][1];
}
}
return maxProfit;
}
int main() {
int difficulty[] = {2, 4, 6, 8, 10};
int profit[] = {10, 20, 30, 40, 50};
int worker[] = {4, 5, 6, 7};
int maxProfit = maxProfitAssignment(difficulty, 5, profit, 5, worker, 4);
printf("Max Profit: %d\n", maxProfit);
return 0;
}using System;
using System.Linq;
using System.Collections.Generic;
public class Solution {
public int MaxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
var jobs = new List<(int, int)>();
for (int i = 0; i < difficulty.Length; i++) {
jobs.Add((difficulty[i], profit[i]));
}
jobs = jobs.OrderBy(j => j.Item1).ToList();
Array.Sort(worker);
int maxProfit = 0, best = 0, j = 0;
foreach (var job in jobs) {
if (job.Item2 > best) {
best = job.Item2;
}
jobs[j++] = (job.Item1, best); // Update the job list with running max profits
}
j = 0;
foreach (int ability in worker) {
while (j < jobs.Count && ability >= jobs[j].Item1) {
++j;
}
if (j > 0) {
maxProfit += jobs[j - 1].Item2;
}
}
return maxProfit;
}
public static void Main() {
var solution = new Solution();
Console.WriteLine(solution.MaxProfitAssignment(new int[] {2, 4, 6, 8, 10}, new int[] {10, 20, 30, 40, 50}, new int[] {4, 5, 6, 7}));
}
}This Python implementation precomputes the maximum possible profit up to each job using sorted resources. Workers access these precomputed profits for optimal matching in a streamlined search.
Time Complexity: O(n log n + m log m)
Space Complexity: O(n)
Approach 3: Sorting + Two Pointers
We can sort the jobs in ascending order of ability, and then sort the jobs in ascending order of difficulty.
Then we traverse the workers. For each worker, we find the job with the maximum profit that he can complete, and then add this profit to the answer.
The time complexity is O(n times log n + m times log m), and the space complexity is O(n). Where n and m are the lengths of the arrays profit and worker respectively.
function maxProfitAssignment(difficulty: number[], profit: number[], worker: number[]): number {
const n = profit.length;
worker.sort((a, b) => a - b);
const jobs = Array.from({ length: n }, (_, i) => [difficulty[i], profit[i]]);
jobs.sort((a, b) => a[0] - b[0]);
let [ans, mx, i] = [0, 0, 0];
for (const w of worker) {
while (i < n && jobs[i][0] <= w) {
mx = Math.max(mx, jobs[i++][1]);
}
ans += mx;
}
return ans;
}func maxProfitAssignment(difficulty []int, profit []int, worker []int) (ans int) {
sort.Ints(worker)
n := len(profit)
jobs := make([][2]int, n)
for i, p := range profit {
jobs[i] = [2]int{difficulty[i], p}
}
sort.Slice(jobs, func(i, j int) bool { return jobs[i][0] < jobs[j][0] })
mx, i := 0, 0
for _, w := range worker {
for ; i < n && jobs[i][0] <= w; i++ {
mx = max(mx, jobs[i][1])
}
ans += mx
}
return
}Approach 4: Dynamic Programming
Let's denote m = max(difficulty) and define an array f of length m + 1, where f[i] represents the maximum profit among jobs with difficulty less than or equal to i, initially f[i] = 0.
Then, we iterate over the jobs, and for each job (d, p), if d leq m, we update f[d] = max(f[d], p).
Next, we iterate from 1 to m, and for each i, we update f[i] = max(f[i], f[i - 1]).
Finally, we iterate over the workers, and for each worker w, we add f[w] to the answer.
The time complexity is O(n + M), and the space complexity is O(M). Here, n is the length of the profit array, and M is the maximum value in the difficulty array.
function maxProfitAssignment(difficulty: number[], profit: number[], worker: number[]): number {
const m = Math.max(...difficulty);
const f = Array(m + 1).fill(0);
const n = profit.length;
for (let i = 0; i < n; ++i) {
const d = difficulty[i];
f[d] = Math.max(f[d], profit[i]);
}
for (let i = 1; i <= m; ++i) {
f[i] = Math.max(f[i], f[i - 1]);
}
return worker.reduce((acc, w) => acc + f[Math.min(w, m)], 0);
}func maxProfitAssignment(difficulty []int, profit []int, worker []int) (ans int) {
m := slices.Max(difficulty)
f := make([]int, m+1)
for i, d := range difficulty {
f[d] = max(f[d], profit[i])
}
for i := 1; i <= m; i++ {
f[i] = max(f[i], f[i-1])
}
for _, w := range worker {
ans += f[min(w, m)]
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Greedy Matching | Time Complexity: O(n log n + m log m) |
| Approach 2: Efficient Profit Calculation with One Pass | Time Complexity: O(n log n + m log m) |
| Sorting + Two Pointers | – |
| Dynamic Programming | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Most Profit Assigning Work easy or hard?
Most Profit Assigning Work is considered a Medium problem. The challenge lies in recognizing that sorting plus a greedy running maximum removes the need to check every job for every worker, reducing a potential O(n*m) solution to near linear time after sorting.
Most Profit Assigning Work Python/Java solution
Typical implementations pair job difficulty and profit, sort them, and iterate with a pointer while maintaining the best profit seen so far. This approach is commonly implemented in Python, Java, C++, and JavaScript using built-in sorting and simple loops.
How to solve Most Profit Assigning Work in O(n)?
Pure O(n) is not possible for arbitrary inputs because jobs must be ordered by difficulty. However, after sorting jobs and workers, the assignment step becomes O(n + m). A prefix maximum profit array or two-pointer scan allows each worker to be processed in constant time after preprocessing.
What is the best approach for Most Profit Assigning Work?
The most common approach sorts jobs by difficulty and workers by skill, then uses a greedy sweep to track the maximum profit seen so far. As you iterate through workers, you advance through all jobs they can perform and keep the best profit available. This runs in O((n + m) log n) time due to sorting and O(1) extra space.
Is Most Profit Assigning Work asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Amazon and Google because it tests greedy thinking, sorting strategies, and efficient scanning with two pointers. Interviewers use it to evaluate whether candidates can avoid brute-force comparisons.
What data structure is used in Most Profit Assigning Work?
The solution primarily uses arrays combined with sorting and greedy scanning. Some implementations also use prefix arrays for maximum profit tracking or binary search on sorted difficulties for fast lookups.
What is the time complexity of Most Profit Assigning Work?
The optimal solution runs in O((n + m) log n) time where n is the number of jobs and m is the number of workers. The sorting step dominates the runtime, while the greedy scan processes each job and worker once.