826. Most Profit Assigning Work LeetCode Solution

Last updated: February 20, 2025

In this guide, you will get 826. Most Profit Assigning Work LeetCode Solution with the best time and space complexity. The solution to Most Profit Assigning Work problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Most Profit Assigning Work solution in C++
Most Profit Assigning Work solution in Java
Most Profit Assigning Work solution in Python
Additional Resources

826. Most Profit Assigning Work LeetCode Solution image

Problem Statement of Most Profit Assigning Work

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, and
worker[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.

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.length
n == profit.length
m == worker.length
1 <= n, m <= 104
1 <= difficulty[i], profit[i], worker[i] <= 105

Complexity Analysis

Time Complexity: O(n\log n + m\log m)
Space Complexity: O(n)

826. Most Profit Assigning Work LeetCode Solution in C++

class Solution {
 public:
  int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit,
                          vector<int>& worker) {
    int ans = 0;
    vector<pair<int, int>> jobs;

    for (int i = 0; i < difficulty.size(); ++i)
      jobs.emplace_back(difficulty[i], profit[i]);

    ranges::sort(jobs);
    ranges::sort(worker);

    int i = 0;
    int maxProfit = 0;

    for (const int w : worker) {
      for (; i < jobs.size() && w >= jobs[i].first; ++i)
        maxProfit = max(maxProfit, jobs[i].second);
      ans += maxProfit;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

826. Most Profit Assigning Work LeetCode Solution in Java

class Solution {
  public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
    int ans = 0;
    List<Pair<Integer, Integer>> jobs = new ArrayList<>();

    for (int i = 0; i < difficulty.length; ++i)
      jobs.add(new Pair<>(difficulty[i], profit[i]));

    Collections.sort(jobs, Comparator.comparing(Pair::getKey));
    Arrays.sort(worker);

    int i = 0;
    int maxProfit = 0;

    for (final int w : worker) {
      for (; i < jobs.size() && w >= jobs.get(i).getKey(); ++i)
        maxProfit = Math.max(maxProfit, jobs.get(i).getValue());
      ans += maxProfit;
    }

    return ans;
  }
}
// code provided by PROGIEZ

826. Most Profit Assigning Work LeetCode Solution in Python

class Solution:
  def maxProfitAssignment(
      self,
      difficulty: list[int],
      profit: list[int],
      worker: list[int],
  ) -> int:
    ans = 0
    jobs = sorted(zip(difficulty, profit))
    worker.sort(reverse=1)

    i = 0
    maxProfit = 0

    for w in sorted(worker):
      while i < len(jobs) and w >= jobs[i][0]:
        maxProfit = max(maxProfit, jobs[i][1])
        i += 1
      ans += maxProfit

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents