Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

826. Most Profit Assigning Work - Leetcode Solution

Code Implementation

class Solution:
    def maxProfitAssignment(self, difficulty, profit, worker):
        jobs = sorted(zip(difficulty, profit))
        worker.sort()
        res = 0
        best = 0
        i = 0
        n = len(jobs)
        for ability in worker:
            while i < n and jobs[i][0] <= ability:
                best = max(best, jobs[i][1])
                i += 1
            res += best
        return res
      
class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        vector<pair<int,int>> jobs;
        for (int i = 0; i < difficulty.size(); ++i)
            jobs.push_back({difficulty[i], profit[i]});
        sort(jobs.begin(), jobs.end());
        sort(worker.begin(), worker.end());
        int res = 0, best = 0, i = 0, n = jobs.size();
        for (int ability : worker) {
            while (i < n && jobs[i].first <= ability) {
                best = max(best, jobs[i].second);
                ++i;
            }
            res += best;
        }
        return res;
    }
};
      
class Solution {
    public 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 res = 0, best = 0, i = 0;
        for (int ability : worker) {
            while (i < n && jobs[i][0] <= ability) {
                best = Math.max(best, jobs[i][1]);
                ++i;
            }
            res += best;
        }
        return res;
    }
}
      
var maxProfitAssignment = function(difficulty, profit, worker) {
    let jobs = [];
    for (let i = 0; i < difficulty.length; ++i)
        jobs.push([difficulty[i], profit[i]]);
    jobs.sort((a, b) => a[0] - b[0]);
    worker.sort((a, b) => a - b);
    let res = 0, best = 0, i = 0, n = jobs.length;
    for (let ability of worker) {
        while (i < n && jobs[i][0] <= ability) {
            best = Math.max(best, jobs[i][1]);
            ++i;
        }
        res += best;
    }
    return res;
};

Problem Description

Given two arrays difficulty and profit of the same length, where each difficulty[i] is the difficulty of a job and profit[i] is the profit for doing that job, and an array worker representing the ability of each worker, assign jobs to workers to maximize total profit. - Each worker can only do at most one job, and their ability must be at least the job's difficulty. - Each job can be assigned to any number of workers (jobs are not "used up"). - Assign jobs so that each worker gets the job with the highest profit they can do. - Return the maximum total profit that can be achieved by assigning jobs to all workers.

Thought Process

At first glance, one might think to check every job for every worker and assign them the most profitable job they can do. This brute-force approach works but is inefficient, especially with large input sizes. To optimize, we notice:
  • Workers can share jobs; jobs are not exclusive.
  • For each worker, we only care about the most profitable job they can do (difficulty ≤ ability).
  • If we sort jobs by difficulty and workers by ability, we can efficiently match them.
The key idea is to process both lists in order, tracking the best profit available so far for each worker's ability.

Solution Approach

The optimized solution follows these steps:
  1. Pair and Sort Jobs: Combine difficulty and profit into a list of jobs, then sort jobs by difficulty in ascending order.
  2. Sort Workers: Sort the worker array by ability in ascending order.
  3. Iterate Workers: For each worker, process jobs in order of difficulty. For each job whose difficulty is ≤ worker's ability, track the highest profit seen so far.
  4. Assign Best Profit: Assign the highest available profit to the worker. Since jobs are sorted and workers are sorted, we can use a single pass with two pointers.
  5. Accumulate Total: Add up the profits assigned to each worker for the final answer.
This approach ensures each worker gets the best job they can do, and avoids redundant work by leveraging sorting and sequential processing.

Example Walkthrough

Suppose difficulty = [2, 4, 6, 8, 10], profit = [10, 20, 30, 40, 50], and worker = [4, 5, 6, 7].
  • Sort jobs: [(2,10), (4,20), (6,30), (8,40), (10,50)]
  • Sort workers: [4, 5, 6, 7]
  • For each worker:
    • Worker 4: Can do jobs 2 and 4. Highest profit = 20.
    • Worker 5: Can do jobs 2 and 4. Highest profit = 20.
    • Worker 6: Can do jobs 2, 4, and 6. Highest profit = 30.
    • Worker 7: Can do jobs 2, 4, and 6. Highest profit = 30.
  • Total profit = 20 + 20 + 30 + 30 = 100.
The algorithm efficiently matches each worker to their best possible job.

Time and Space Complexity

  • Brute-force approach: For each worker, check all jobs. This is O(N*M), where N = number of workers, M = number of jobs.
  • Optimized approach:
    • Sorting jobs: O(M log M)
    • Sorting workers: O(N log N)
    • Single pass matching: O(N + M)
    Total: O(N log N + M log M)
  • Space: O(M) for job list, plus O(1) extra space otherwise (ignoring input sorting overhead).

Summary

The solution leverages sorting and sequential processing to efficiently assign each worker the most profitable job they can handle. By tracking the best profit as we iterate through sorted jobs and workers, we avoid redundant checks and achieve optimal performance. This approach elegantly balances clarity and efficiency, making it a robust solution for maximizing profit in job assignment problems.