Leetcode #826. Most Profit Assigning Work solution in Java (Sort + Binary Search)

Question

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.

Answer 1

Algorithm

The algorithm is correct, but an optimization is possible. When the input contains multiple jobs with the same difficulty, then you can reduce the search space, because at any difficulty level, you're only interested in the most profitable job. The time complexity would become \$ O(n \log n + w \log n')\$, where \$n'\$ is the number of unique difficulties.

Extract special treatment out of the loop

The loop in updateDifficultyAndMaxProfits has a special treatment for index 0. Instead of evaluating a condition for each iteration of the loop, since the input is guaranteed to have at least 1 element, you could perform the special treatment before the loop begins, and make the loop start from index 1, and no conditional.

Avoid modifying the input

You pass to the method updateDifficultyAndMaxProfits the difficulties array that was an input, and overwrite its content. Although this saved you some space in memory, it may not be acceptable, and not a good practice. It would have been better to pass to the function a new array.

However, with the first tip at the top of this review, this point will no longer matter, because you will need a different approach to store the (difficulty, maxProfit) pairs that avoids redundant difficulty values, and you won't know in advance the number of pairs you will need. You may for example implement a computeDifficultyAndMaxProfits, returning a list of pairs.

How about some streams and lambdas

Some elements of your program can be written more compactly with streams and lambdas, for example:

Job[] jobs = IntStream.range(0, profit.length)
    .mapToObj(i -> new Job(difficulty[i], profit[i]))
    .sorted(Comparator.comparingInt(job -> job.difficulty))
    .toArray(Job[]::new);

Since Job implements Comparable, the custom comparator is not necessary here. Keeping the sorting logic outside the class like this is often more practical. It's also compact to write. If you needed to sort multiple times, you could store the lambda in a variable to avoid duplicating logic.

The final computation could also be written with streams and lambdas compactly:

return IntStream.of(workers)
    .map(w -> computeMaxProfit(w))
    .sum();