Most Profit Assigning Work

MediumProblemExternal linkUpdated Sep 24, 2026

Description

You have n jobs and m workers.

Job i has a difficulty difficulty[i] and pays profit[i].
Worker j has an ability worker[j] and can only do a job whose difficulty is at most that ability.

Each worker does at most one job. A job can be done by any number of workers: if three workers all take the same job paying 5, they earn 15 together. A worker who cannot do any job earns 0.

Assign the workers so that the total pay is as large as possible, and return that total.

Examples

Example 1

Input: difficulty = [5, 2, 8, 4], profit = [30, 10, 25, 40], worker = [3, 6, 9, 1]

Output: 90

Explanation: Each worker simply takes the best-paying job they are able to do:

Ability 3: only the difficulty-2 job is easy enough → 10.
Ability 6: the jobs of difficulty 5, 2 and 4 are easy enough; the best pays 40 → 40.
Ability 9: every job is easy enough, and the best still pays 40. The hardest job, difficulty 8, pays only 25, so a harder job is not always better → 40.
Ability 1: no job is easy enough → 0.

Total: 10 + 40 + 40 + 0 = 90.

Example 2

Input: difficulty = [3, 3], profit = [7, 9], worker = [3, 3, 3]

Output: 27

Explanation: Two jobs share difficulty 3. All three workers can do both, and all three take the one paying 9. A job can be done by any number of workers: 9 + 9 + 9 = 27.

Example 3

Input: difficulty = [10, 20], profit = [5, 8], worker = [4, 9]

Output: 0

Explanation: Both jobs are harder than both workers, so nobody can work.

Constraints

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

Editorial

Brute Force

Intuition

Workers do not compete with each other: a job can be done by any number of them, and nobody's choice limits anyone else's. So the total is largest when every worker takes the best-paying job they can do. Each worker is a small problem of their own.

The most direct way to solve it: for each worker, look at every job, skip the ones that are too hard, and keep the highest pay among the rest. A worker who finds nothing earns 0.

Step-by-Step Explanation

We trace Example 1. The first worker checks the four jobs one by one; the other three workers do the same, shown one step each.

Step 1: The jobs are (difficulty 5, pay 30), (2, 10), (8, 25) and (4, 40). The total starts at 0.

Step 2: Worker 3, job 0: difficulty 5 > 3, too hard.

Step 3: Worker 3, job 1: difficulty 2 ≤ 3, pay 10 — the best so far.

Step 4: Worker 3, job 2: difficulty 8 > 3, too hard.

Step 5: Worker 3, job 3: difficulty 4 > 3, too hard. This worker earns 10; total 10.

Step 6: Worker 6: the jobs of difficulty 5, 2, 4 are easy enough; the best pays 40 — earns 40; total 50.

Step 7: Worker 9: the jobs of difficulty 5, 2, 8, 4 are easy enough; the best pays 40 — earns 40; total 90.

Step 8: Worker 1: every job is too hard — earns 0; total 90.

Step 9: Return 90 = 10 + 40 + 40 + 0, after 4 × 4 = 16 checks.

Brute Force — Every Worker Checks Every Job — Top row: each job's difficulty; bottom row: its pay. Amber jobs are too hard for the worker, green is the best pay they can reach.

Algorithm

Set total = 0.
For each worker's ability:
- Set best = 0.
- For each job (d, p): if d ≤ ability, set best = max(best, p).
- Add best to total.
Return total.

Code

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int total = 0;
        for (int ability : worker) {
            int best = 0;  // a worker who can do no job earns 0
            for (int i = 0; i < (int)difficulty.size(); i++)
                if (difficulty[i] <= ability) best = max(best, profit[i]);
            total += best;
        }
        return total;
    }
};

class Solution:
    def maxProfitAssignment(self, difficulty: list[int], profit: list[int], worker: list[int]) -> int:
        total = 0
        for ability in worker:
            best = 0  # a worker who can do no job earns 0
            for d, p in zip(difficulty, profit):
                if d <= ability:
                    best = max(best, p)
            total += best
        return total

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int total = 0;
        for (int ability : worker) {
            int best = 0;  // a worker who can do no job earns 0
            for (int i = 0; i < difficulty.length; i++)
                if (difficulty[i] <= ability) best = Math.max(best, profit[i]);
            total += best;
        }
        return total;
    }
}

Complexity Analysis

Let n be the number of jobs and m the number of workers.

Time Complexity: O(n · m). Every worker checks every job.

Space Complexity: O(1). Only a few running totals.

Why This Approach Is Not Efficient

With 10^4 jobs and 10^4 workers, that is 10^4 × 10^4 = 10^8 checks. Measured at that size, it takes about 2 seconds in Python (0.1 s in C++).

The waste is that every worker asks almost the same question, "the best pay among jobs no harder than me", and each one answers it from scratch. A worker with ability 9 rechecks every job a worker with ability 6 already checked, just to find the same 40.

That question has a shape we can use. As ability grows, more jobs become possible, so the best pay can only stay the same or go up. It is a staircase that never steps down. If we build that staircase once, every worker can simply read it off.

Better Approach - Sort the Jobs, Keep a Running Best, Binary Search

Intuition

Build the staircase once, then let every worker read it.

Sort the jobs by difficulty, easiest first.
Walk the sorted jobs keeping a running best pay. After each job, record the best pay among that job and every easier one. Because the running best never goes down, a hard job that pays less than an easier one simply leaves the staircase flat.

A chart of Example 1: the jobs are dots at difficulty 2 paying 10, 4 paying 40, 5 paying 30 and 8 paying 25. A green staircase shows the best pay available at each difficulty: 0, then 10 from difficulty 2, then 40 from difficulty 4 onward. The two harder jobs that pay less sit under it. Workers of ability 1, 3, 6 and 9 read the staircase at 0, 10, 40 and 40, a total of 90.

For each worker, find how many jobs are easy enough, meaning how many sorted difficulties are ≤ their ability. Their pay is the running best at the last of those jobs, or 0 if there are none.

The difficulties are sorted, so step 3 is a binary search. Look at the middle job. If it is easy enough, so is everything before it, and the answer lies to the right. Otherwise it and everything after it are too hard, and the answer lies to the left. Each look halves what is left, so about 14 looks are enough for 10^4 jobs.

Step-by-Step Explanation

We trace Example 1 again. After sorting, the three rows are difficulty, pay, and the running best. The first worker's binary search is shown look by look.

Step 1: Sort the jobs by difficulty: (2, 10), (4, 40), (5, 30), (8, 25).

Step 2: Difficulty 2 pays 10: the best so far becomes 10.

Step 3: Difficulty 4 pays 40: the best so far becomes 40.

Step 4: Difficulty 5 pays 30, less than 40: the best so far stays 40.

Step 5: Difficulty 8 pays 25, less than 40: the best so far stays 40.

Step 6: Worker 3: start with lo = 0 and hi = 4. The middle difficulty 5 > 3, so the answer lies to the left — hi = 2.

Step 7: Worker 3: middle difficulty 4 > 3, so the answer lies to the left — hi = 1.

Step 8: Worker 3: middle difficulty 2 ≤ 3, so the answer lies to the right — lo = 1. So 1 job is easy enough and the worker earns 10.

Step 9: Worker 6: the search finds 3 easy-enough jobs → earns 40; total 50.

Step 10: Worker 9: the search finds 4 easy-enough jobs → earns 40; total 90.

Step 11: Worker 1: no job is easy enough → earns 0; total 90.

Step 12: Return 90.

Sorted Jobs, a Running Best, and a Binary Search — Rows: difficulty, pay, and the best pay among that job and all easier ones. Each worker binary-searches the difficulties and reads the bottom row.

Algorithm

Sort the jobs (difficulty, profit) by difficulty.
Walk them in order with running = 0. At job i, set running = max(running, profit) and store diffs[i] = difficulty and best_so_far[i] = running.
For each worker's ability:
- k = the number of entries in diffs that are ≤ ability (binary search).
- If k > 0, add best_so_far[k − 1] to the total.
Return the total.

Code

#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int n = difficulty.size();
        vector<pair<int, int>> jobs(n);
        for (int i = 0; i < n; i++) jobs[i] = {difficulty[i], profit[i]};
        sort(jobs.begin(), jobs.end());  // easiest first
        vector<int> diffs(n), bestSoFar(n);
        int running = 0;
        for (int i = 0; i < n; i++) {
            running = max(running, jobs[i].second);  // the best pay among all jobs this easy or easier
            diffs[i] = jobs[i].first;
            bestSoFar[i] = running;
        }
        int total = 0;
        for (int ability : worker) {
            int k = upper_bound(diffs.begin(), diffs.end(), ability) - diffs.begin();  // how many jobs are easy enough
            if (k > 0) total += bestSoFar[k - 1];
        }
        return total;
    }
};

import bisect


class Solution:
    def maxProfitAssignment(self, difficulty: list[int], profit: list[int], worker: list[int]) -> int:
        jobs = sorted(zip(difficulty, profit))  # easiest first
        diffs, best_so_far = [], []
        running = 0
        for d, p in jobs:
            running = max(running, p)  # the best pay among all jobs this easy or easier
            diffs.append(d)
            best_so_far.append(running)
        total = 0
        for ability in worker:
            k = bisect.bisect_right(diffs, ability)  # how many jobs are easy enough
            if k > 0:
                total += best_so_far[k - 1]
        return total

import java.util.Arrays;

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        int[][] jobs = new int[n][];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{difficulty[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));  // easiest first
        int[] diffs = new int[n], bestSoFar = new int[n];
        int running = 0;
        for (int i = 0; i < n; i++) {
            running = Math.max(running, jobs[i][1]);  // the best pay among all jobs this easy or easier
            diffs[i] = jobs[i][0];
            bestSoFar[i] = running;
        }
        int total = 0;
        for (int ability : worker) {
            int k = countAtMost(diffs, ability);  // how many jobs are easy enough
            if (k > 0) total += bestSoFar[k - 1];
        }
        return total;
    }

    // Binary search: the number of values in the sorted array that are <= x.
    private int countAtMost(int[] sorted, int x) {
        int lo = 0, hi = sorted.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (sorted[mid] <= x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

Complexity Analysis

Let n be the number of jobs and m the number of workers.

Time Complexity: O(n log n + m log n). Sorting costs n log n, the running best is one pass over the jobs, and each worker does one binary search of about log n looks. At full size that is roughly 10^4 × 14 + 10^4 × 14 steps instead of 10^8. Measured, it takes about 4 ms in Python.

Space Complexity: O(n) for the sorted jobs and the running best.

A common variation sorts the workers too and walks both lists together with two pointers instead of binary searching. It costs about the same, O(n log n + m log m).

Why This Approach Is Not Efficient

At this problem's limits the sorted approach is already fast, and it is the right choice whenever difficulties can be huge numbers. Here, though, every value is a whole number no larger than 10^5, and that opens a shortcut.

The sort and the binary searches exist only to find a worker's place on the staircase. If we simply stored the staircase at every whole-number difficulty from 0 to 10^5, a worker with ability a could read position a directly. There would be no sorting and no searching.

Optimal Approach - A Best-Pay Table for Every Difficulty

Intuition

Make a table best with one slot for every difficulty from 0 up to the largest value in the input.

Drop each job into its slot. Slot d keeps the highest pay among jobs of difficulty exactly d. Two jobs with the same difficulty keep the better one.
Carry the best pay rightward. Walk the slots from left to right with best[x] = max(best[x], best[x − 1]). Every job counted in slot x − 1 is easier than x, so it can be done at x too. After this pass, best[x] is exactly the staircase value, the best pay among all jobs no harder than x.
Each worker reads one slot. A worker with ability a earns best[a].

Step-by-Step Explanation

We trace Example 1 once more. Each cell is one difficulty slot from 0 to 9; the highlighted cell is the one being written or read, and the formula underneath shows the calculation.

Step 1: Make a table best with one slot for each difficulty 0 to 9, all 0.

Step 2: Job (difficulty 5, pay 30) → best[5] = 30.

Step 3: Job (difficulty 2, pay 10) → best[2] = 10.

Step 4: Job (difficulty 8, pay 25) → best[8] = 25.

Step 5: Job (difficulty 4, pay 40) → best[4] = 40.

Step 6: best[1] = max(0, 0) = 0.

Step 7: best[2] = max(10, 0) = 10.

Step 8: best[3] = max(0, 10) = 10 — the easier job wins.

Step 9: best[4] = max(40, 10) = 40.

Step 10: best[5] = max(30, 40) = 40 — the easier job wins.

Step 11: best[6] = max(0, 40) = 40 — the easier job wins.

Step 12: best[7] = max(0, 40) = 40 — the easier job wins.

Step 13: best[8] = max(25, 40) = 40 — the easier job wins.

Step 14: best[9] = max(0, 40) = 40 — the easier job wins.

Step 15: Worker 3 earns best[3] = 10; total 10.

Step 16: Worker 6 earns best[6] = 40; total 50.

Step 17: Worker 9 earns best[9] = 40; total 90.

Step 18: Worker 1 earns best[1] = 0; total 90.

Step 19: Return 90.

A Best-Pay Table With One Slot per Difficulty — Jobs are dropped into the slot for their difficulty, one pass carries the best pay rightward, and each worker reads the slot for their ability.

Algorithm

Let size = the largest value among difficulty and worker, plus 1. Create best of that size, all 0.
For each job (d, p): best[d] = max(best[d], p).
For x from 1 to size − 1: best[x] = max(best[x], best[x − 1]).
Return the sum of best[a] over every worker's ability a.

Code

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        // Every value is a whole number up to 10^5, so keep one slot per difficulty.
        int size = max(*max_element(difficulty.begin(), difficulty.end()),
                       *max_element(worker.begin(), worker.end())) + 1;
        vector<int> best(size, 0);
        for (int i = 0; i < (int)difficulty.size(); i++)
            best[difficulty[i]] = max(best[difficulty[i]], profit[i]);  // the best job at exactly this difficulty
        for (int x = 1; x < size; x++)
            best[x] = max(best[x], best[x - 1]);  // ... or at any easier difficulty
        int total = 0;
        for (int ability : worker) total += best[ability];
        return total;
    }
};

class Solution:
    def maxProfitAssignment(self, difficulty: list[int], profit: list[int], worker: list[int]) -> int:
        # Every value is a whole number up to 10^5, so keep one slot per difficulty.
        size = max(max(difficulty), max(worker)) + 1
        best = [0] * size
        for d, p in zip(difficulty, profit):
            best[d] = max(best[d], p)  # the best job at exactly this difficulty
        for x in range(1, size):
            best[x] = max(best[x], best[x - 1])  # ... or at any easier difficulty
        return sum(best[a] for a in worker)

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        // Every value is a whole number up to 10^5, so keep one slot per difficulty.
        int size = 0;
        for (int d : difficulty) size = Math.max(size, d);
        for (int a : worker) size = Math.max(size, a);
        int[] best = new int[size + 1];
        for (int i = 0; i < difficulty.length; i++)
            best[difficulty[i]] = Math.max(best[difficulty[i]], profit[i]);  // the best job at exactly this difficulty
        for (int x = 1; x <= size; x++)
            best[x] = Math.max(best[x], best[x - 1]);  // ... or at any easier difficulty
        int total = 0;
        for (int ability : worker) total += best[ability];
        return total;
    }
}

Complexity Analysis

Let n be the number of jobs, m the number of workers and V the largest value, at most 10^5.

Time Complexity: O(n + m + V). One pass drops the jobs in, one pass over the V slots builds the staircase, and each worker is a single lookup. Nothing is sorted.

Space Complexity: O(V) for the table, 10^5 + 1 integers at most.

How the two compare. At this problem's limits, the table and the sorted approach both finish in about 4 ms in Python. The difference shows when there are many more jobs and workers: with a million of each, and values still at most 10^5, we measured 71 ms for the table against 1.13 s for the sorted approach. The table's cost depends on V, though. If difficulties could be as large as 10^9, the table would be far too big, and the sorted approach would be the right one.