Return to Revisions

Problem Statement:

We have jobs: difficulty[i] is the difficulty of the i^th job, and profit[i] is the profit of the i^th job.

Now we have some workers. worker[i] is the ability of the i^th worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays 1,ドル then the total profit will be 3ドル. If a worker cannot complete any job, his profit is 0ドル.

What is the most profit we can make?

###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 profit of [20,20,30,30] seperately.

###Notes:

• 1 <= difficulty.length = profit.length <= 10000
• 1 <= worker.length <= 10000
• difficulty[i], profit[i], worker[i] are in range [1, 10^5]

Solution:

• Time Complexity: O(n log n + w log n).
• Space Complexity: O(n).

class Solution {
 private static class Job implements Comparable<Job> {
 private int difficulty;
 private int profit;
 
 public Job(int difficulty, int profit) {
 this.difficulty = difficulty;
 this.profit = profit;
 }
 
 public int getDifficulty() {
 return difficulty;
 }
 
 public int getProfit() {
 return profit;
 }
 
 //Jobs are ordered based on their difficulties
 @Override
 public int compareTo(Job otherJob) {
 int difference = this.getDifficulty() - otherJob.getDifficulty();
 
 //If both the jobs have the same difficulty, we want the more profitable job to be ordered first so that we get correct maxProfits
 difference = (difference == 0) ? (otherJob.getProfit() - this.getProfit()) : difference;
 
 return difference;
 }
 }
 
 private void updateDifficultyAndMaxProfits(Job[] jobs, int[] difficulties, int[] maxProfits) {
 for (int i = 0; i < jobs.length; i++) {
 Job job = jobs[i];
 difficulties[i] = job.getDifficulty();
 if (i == 0) {
 maxProfits[i] = job.getProfit();
 } else {
 maxProfits[i] = Math.max(job.getProfit(), maxProfits[i - 1]);
 }
 }
 }
 
 public int maxProfitAssignment(int[] difficulties, int[] profits, int[] workers) {
 Job[] jobs = new Job[difficulties.length];
 
 for (int i = 0; i < difficulties.length; i++) {
 jobs[i] = new Job(difficulties[i], profits[i]);
 }
 
 Arrays.sort(jobs);
 
 int[] maxProfits = new int[difficulties.length];
 updateDifficultyAndMaxProfits(jobs, difficulties, maxProfits);
 
 int totalMaxProfit = 0;
 
 for (int worker : workers) {
 int workerMaxProfitIndex = Arrays.binarySearch(difficulties, worker);
 
 //If there isn't an exact match we need to retrieve the index from the insertion point
 if (workerMaxProfitIndex < 0) {
 workerMaxProfitIndex = -(workerMaxProfitIndex + 2);
 }
 
 //Update totalMaxProfit only if there's at least one task that the worker can accomplish
 if(workerMaxProfitIndex >= 0){
 totalMaxProfit += maxProfits[workerMaxProfitIndex];
 }
 }
 
 return totalMaxProfit;
 }
}

Please review my code and let me know if there's room for improvement.