Problem

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.

Examples

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

Solution

Method 1 - Sorting

Lets take the examples: difficulty = [68,35,52,47,86], profit = [67,17,1,81,3], worker = [92,10,85,84,82]

  • First thing we do is sort the {difficulty[i], profit[i]} pair based on difficulty, because we are given the worker array as the job difficulty handling ability of worker. Then we get following arrays: difficulty = [35,47,52,68,86], profit = [17,81,1,67,3]
  • Now, if a worker can do a job at difficulty level A then they can do all the jobs with difficulty less than or equal to A. For eg. A = 52, the worker can handle difficulty [35, 47, 52] and profits [17, 81, 1] and we get the a maximum profit as 81.
  • So, we update the profit values with the maximum profit from previous ones.
    • profit[i] = max(profit[i], profit[i - 1]) ⇨ We loop from left to right t
    • profit = [17, 81, 81, 81, 81]
  • Now we can apply binary search(upper bound) for every worker and individually assign jobs finally get the max profit.
    • difficulty = [35,47,52,68,86], profit = [17, 81, 81, 81, 81]
    • worker = [92,10,85,84,82]
    • Defile maxProfit = 0
    • i = 0, worker[i] = 92 ⇨ we try to find the highest difficulty less than or equal to 92, which return 86 and profit associated to it is 81. maxProfit += 81 = 0
    • i = 1, worker = 10 ⇨ We couldn’t find any job that can be done by worker with ability 10.
    • i = 2, worker[i] = 85 ⇨ we try to find the highest difficulty less than or equal to 85, which return 68 and profit associated to it is 81. maxProfit += 81 = 162
    • i = 3, worker[i] = 84 ⇨ we try to find the highest difficulty less than or equal to 84, which return 68 and profit associated to it is 81. maxProfit += 81 = 243
    • i = 4, worker[i] = 82 ⇨ we try to find the highest difficulty less than or equal to 82, which return 68 and profit associated to it is 81. maxProfit += 81 = 324
  • So, we return maxProfit of 324

Here is the video explanation of the same:

Code

Java
public class Solution {
	static class Job {
		int difficulty;
		int profit;

		public Job(int difficulty, int profit) {
			this.difficulty = difficulty;
			this.profit = profit;
		}
	}

	public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
		int n = difficulty.length;
		Job[] jobs = new Job[n];

		for (int i = 0; i < n; i++) {
			jobs[i] = new Job(difficulty[i], profit[i]);
		}

		Arrays.sort(jobs, Comparator.comparingInt(a -> a.difficulty));

		for (int i = 1; i < n; i++) {
			jobs[i].profit = Math.max(jobs[i].profit, jobs[i - 1].profit);
		}

		int maxProfit = 0;

		for (int ability: worker) {
			int low = 0;
			int high = n - 1;
			int currProfit = 0; 

			// Binary search to find the highest difficulty job that is less than
			// or equal to the worker's ability
			while (low <= high) {
				int mid = low + (high - low) / 2;

				if (jobs[mid].difficulty <= ability) {
					// If the job difficulty is less than or equal to the worker's ability,
					// Update the tempProfit and search for a more difficult job
					low = mid + 1;
					currProfit = jobs[mid].profit;
				} else {
					high = mid - 1;
				}
			}
			// Accumulate the profit if the job was found
			maxProfit += currProfit;
		}

		return maxProfit;
	}
}

Complexity

  • ⏰ Time complexity: O((n + m) log n) where n is number of jobs, and m is number of workers. The reason is we sort the jobs array, which takes O(n log n), then we update profit array, which takes O(n) time, finally we apply binary search for m workers in jobs.difficulty array, which takes m log n time. So, we sum up O(n log n) + O(n) + O(m log n) = O( (n + m) log n)
  • 🧺 Space complexity: O(n) as we are creating new job array to store difficulty and profit pair.