826. Most Profit Assigning Work

MediumGreedyArrayTwo PointersBinary SearchSorting

Problem Description

You are given a scenario where there are n different jobs and m workers. Each job has a difficulty level and a profit associated with it. These are listed in the arrays difficulty and profit respectively, where difficulty[i] represents the difficulty of the i-th job, and profit[i] represents the profit for completing the i-th job. There's also a worker array where worker[j] indicates the maximum job difficulty that the j-th worker can handle.

A worker can only be assigned to a job if the job's difficulty is less than or equal to the worker's ability. Also, a worker can only do one job while a job can be completed by multiple workers. The objective is to maximize the total profit gained by assigning workers to jobs.

Intuition

To find the maximum profit, we should assign the most profitable jobs that workers can perform to them. However, since the jobs and workers are unsorted and a worker can only perform jobs up to their ability, we need an efficient way to match workers with their best possible job.

The intuition behind the solution is to first sort the jobs based on their difficulty, ensuring that we always encounter the less difficult jobs first. Simultaneously, we sort the workers based on their ability so we can sequentially assign them to jobs without backtracking. After this, we can iterate through the workers in ascending order of their ability.

For each worker, we iterate through the sorted jobs, updating the maximum profit (t) that this worker can generate (only if the job difficulty is less than or equal to the worker's ability). Since the jobs are sorted by difficulty, once a job's difficulty is greater than a worker's ability, we can stop the search for that worker and proceed to the next one, because all subsequent jobs will also be too difficult.

As we find the best job for each worker, we accumulate the total profit (res). Once all workers have been assigned jobs (or determined they cannot complete any jobs), the accumulated res will contain the maximum total profit that can be achieved.

Learn more about Greedy, Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation of the solution follows these steps:

Preparation of Job Data: Before we start assigning jobs to the workers, we need to prepare the job data. We do this by pairing each job's difficulty with its profit, creating a list of tuples (difficulty[i], profit[i]), and sorting this list by difficulty. By doing so, we ensure that when we go through the jobs for a worker, we start with the easiest job that provides profit and work our way up.
Sorting Workers: We sort the worker array. This sorting is crucial because it allows us to linearly assign jobs to each worker without the need to check all jobs for every worker. Since the workers are sorted by their ability, once a worker can't do a specific job, we know that all following workers won't be able to do that job either (since they will be more skilled).
Iterating and Matching Jobs to Workers: We go through each worker in ascending order and try to find the most profitable job that they can perform. An index i keeps track of the current job, and for each worker, we check jobs starting from this index. When we encounter a job that the worker can do, we update t to the maximum profit seen so far. The t value represents the best profit a worker with current ability can earn. By doing this, we won't miss any less difficult, higher-paying jobs.
Accumulating Profit: As we find the right job for each worker, we increment the total profit res by t, which at this point would have the highest possible profit that a worker could make according to their ability.
Returning the results: After we have gone through all workers and maximized each of their profits, the variable res holds the maximum total profit that can be achieved, which we return as the final result.

The solution utilizes greedy algorithms and sorts as the core patterns. Greedy algorithms are employed to ensure we are getting the maximum profit per worker before moving on.

The data structures used include arrays/lists and tuples. Arrays/lists are mainly for recording workers' abilities, job difficulty, and profit, while tuples are used for pairing difficulty and profit for more convenient sorting and iteration.

Excellent use of Python's built-in sorting functionality and a double-pointer pattern allows the algorithm to efficiently match workers to jobs with a complexity of O(n log n + m log m) where n is the number of jobs, and m is the number of workers. This is because the sorting operations dominate the overall complexity. The linear pass used to match workers to jobs does not increase the complexity as it's bounded by O(n + m) which is less than the sorting complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach as described above.

Suppose we have the following job difficulties and profits, and worker capabilities:

difficulty = [2, 4, 6, 8]
profit = [20, 40, 70, 80]
worker = [2, 7, 5]

Following the steps from the solution approach:

Step 1: Preparation of Job Data Pair up the job difficulties with the corresponding profits and sort them:

Job data before sorting: [(2, 20), (4, 40), (6, 70), (8, 80)]

After sorting by difficulty: [(2, 20), (4, 40), (6, 70), (8, 80)]

In this case, the list is already sorted by difficulty.

Step 2: Sorting Workers Sort the worker array by their ability:

Workers before sorting: [2, 7, 5]

After sorting: [2, 5, 7]

Step 3: Iterating and Matching Jobs to Workers Now we iterate over each worker and find the highest profit job they can do:

For the first worker (ability = 2), the best job they can do is the one with difficulty 2 and profit 20. We set t = 20.
For the second worker (ability = 5), they can also do the job with difficulty 4, which has a profit of 40. But since the job with difficulty 2 and a profit of 20 (from the previous computation) is in their range, we compare profits and still set t = 40 as it's higher.
For the third worker (ability = 7), they can do the jobs with difficulty 2, 4, and 6. The job with difficulty 6 offers a profit of 70, which is the highest they can earn, so we update t = 70.

Step 4: Accumulating Profit We add up the profits calculated by t for each worker:

Total profit res = 20 (first worker) + 40 (second worker) + 70 (third worker) = 130.

Step 5: Returning the results The maximum total profit that can be achieved with the given workers is res = 130.

In this example, each worker was matched to the most profitable job they could do following a greedy approach, which was facilitated by sorting both the job pairs and the workers to make iteration straightforward and efficient. The final total profit is maximized as required by the problem statement.

Solution Implementation

1from typing import List
2
3class Solution:
4    def max_profit_assignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
5        job_count = len(difficulty)
6        # Pairing each job's difficulty with its profit and storing them as tuples
7        jobs = [(difficulty[i], profit[i]) for i in range(job_count)]
8        # Sorting jobs based on their difficulty
9        jobs.sort(key=lambda x: x[0])
10        # Sorting workers based on their capabilities
11        worker.sort()
12      
13        max_profit = 0  # Tracks the maximum profit that can be achieved so far
14        total_profit = 0  # Summing up the total profit for all workers
15        job_index = 0  # Index to keep track of the current job
16
17        # Iterating through each worker
18        for capability in worker:
19            # Updating the max_profit by comparing with each job's profit if the worker can handle the job
20            while job_index < job_count and jobs[job_index][0] <= capability:
21                max_profit = max(max_profit, jobs[job_index][1])
22                job_index += 1
23            # Accumulating the profit earned by this worker based on max_profit so far
24            total_profit += max_profit
25      
26        # Returning the total profit that can be earned by all workers
27        return total_profit
28

1class Solution {
2    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
3        int jobCount = difficulty.length; // The total number of jobs
4        List<int[]> jobs = new ArrayList<>(); // A list to hold jobs with their difficulty and profit
5      
6        // Add each job's difficulty and profit as int array to the jobs list
7        for (int i = 0; i < jobCount; ++i) {
8            jobs.add(new int[] {difficulty[i], profit[i]});
9        }
10      
11        // Sort the jobs list by their difficulty
12        jobs.sort(Comparator.comparing(a -> a[0]));
13      
14        // Sort the worker array to prepare for the job assignment
15        Arrays.sort(worker);
16      
17        int totalProfit = 0; // Variable to keep track of the total profit
18        int maxProfit = 0;  // Variable to keep track of the maximum profit found so far
19        int jobIndex = 0;   // Index to iterate through the sorted jobs
20      
21        // Iterate through each worker's ability
22        for (int ability : worker) {
23            // While the job index is within bounds and the worker can handle the job difficulty
24            while (jobIndex < jobCount && jobs.get(jobIndex)[0] <= ability) {
25                // Update the maximum profit if the current job offers more 
26                maxProfit = Math.max(maxProfit, jobs.get(jobIndex)[1]);
27                jobIndex++; // Move to the next job
28            }
29            // Sum up the maximum profit the worker can make
30            totalProfit += maxProfit;
31        }
32      
33        return totalProfit; // Return the total profit from all workers
34    }
35}
36

1#include <vector> // Required for using the vector
2#include <algorithm> // Required for using the sort and max functions
3
4class Solution {
5public:
6    int maxProfitAssignment(std::vector<int>& difficulties, std::vector<int>& profits, std::vector<int>& workers) {
7        int numJobs = difficulties.size();
8        std::vector<std::pair<int, int>> jobs; // Pairing each difficulty with its profit
9      
10        // Create a job list by pairing difficulties with profits
11        for (int i = 0; i < numJobs; ++i) {
12            jobs.push_back({difficulties[i], profits[i]});
13        }
14      
15        // Sort the jobs based on difficulty (the first element of the pair)
16        std::sort(jobs.begin(), jobs.end());
17      
18        // Sort the workers based on their ability level
19        std::sort(workers.begin(), workers.end());
20      
21        int maxProfit = 0; // To keep track of the maximum profit that can be earned
22        int jobIndex = 0; // Index to iterate through the sorted jobs
23        int bestProfit = 0; // Keeps the best profit at current worker's difficulty level or below
24      
25        // for every worker, find the best job that the worker can perform
26        for (auto workerAbility : workers) {
27            // Keep updating the best profit while the worker's ability is higher or equal to the difficulty
28            while (jobIndex < numJobs && jobs[jobIndex].first <= workerAbility) {
29                bestProfit = std::max(bestProfit, jobs[jobIndex].second);
30                jobIndex++;
31            }
32            // After finding the best profit for the current worker, add it to the total maxProfit
33            maxProfit += bestProfit;
34        }
35        return maxProfit; // Return the total max profit that can be earned
36    }
37};
38

1// Importing the required functionalities from standard libraries
2import { max, sortBy } from 'lodash';
3
4// Structure to hold a job with its difficulty and profit
5interface Job {
6  difficulty: number;
7  profit: number;
8}
9
10// Function to calculate the maximum profit that can be earned by assigning jobs to workers
11function maxProfitAssignment(
12  difficulties: number[], 
13  profits: number[], 
14  workers: number[]
15): number {
16  const numJobs = difficulties.length;
17  const jobs: Job[] = [];
18
19  // Creating an array of jobs by pairing difficulties with profits
20  for (let i = 0; i < numJobs; i++) {
21    jobs.push({ difficulty: difficulties[i], profit: profits[i] });
22  }
23
24  // Sorting the jobs based on difficulty
25  sortBy(jobs, job => job.difficulty);
26
27  // Sorting the workers based on their ability level
28  sortBy(workers);
29
30  let maxProfit = 0; // Variable to keep track of the maximum profit
31  let jobIndex = 0;  // Index to iterate through the sorted jobs
32  let bestProfit = 0; // Keeps the best profit at the current or a lower difficulty level
33
34  // Iterate over each worker to find the best job they can perform
35  for (const workerAbility of workers) {
36    // Update the best profit while the worker's ability is higher or equal to the job's difficulty
37    while (jobIndex < numJobs && jobs[jobIndex].difficulty <= workerAbility) {
38      bestProfit = max([bestProfit, jobs[jobIndex].profit])!;
39      jobIndex++;
40    }
41    // After finding the best profit for the current worker, add it to maxProfit
42    maxProfit += bestProfit;
43  }
44
45  return maxProfit; // Return the total maximum profit that can be earned
46}
47

Time and Space Complexity

Time Complexity

The given code consists of the following steps contributing to the time complexity:

Pairing the difficulty and profit and creating a job list: This runs in O(n) time, where n is the length of the difficulty list (assuming profit is of the same length).
Sorting the job list: This is the most time-consuming step and it runs in O(n log n) time.
Sorting the worker list: This also runs in O(m log m) time, where m is the number of workers.
Iterating over the sorted worker list and updating total profit: In the worst case, each worker runs through the entire job list, resulting in a potential O(m * n) time complexity, but due to the sorting and one traversal mechanism, this is reduced to O(m + n) since each job is looked at most once.

The combined time complexity from these steps would be linearithmic in the larger of the two input sizes, hence the total time complexity is O(max(m, n) log max(m, n)).

Space Complexity

The space complexity is analyzed by looking at the extra space being used besides the input:

Temporary variables i, t, and res use constant space O(1).
The job list which pairs difficulty with profit: Since it creates a new list of tuples, it takes O(n) additional space.
No additional space is used that grows with the size of the input other than the job list.

Hence, the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: