Problem Description

You are given information about n jobs and m workers, represented by three arrays:

• difficulty[i]: the difficulty level of the i-th job
• profit[i]: the profit earned from completing the i-th job
• worker[j]: the maximum difficulty level that the j-th worker can handle

The key rules are:

1. Worker Capability: A worker can only complete jobs whose difficulty is at most their ability level. For example, if worker[j] = 5, they can only do jobs with difficulty ≤ 5.

2. Assignment Constraints: Each worker can be assigned to at most one job (or no job at all).

3. Job Reusability: The same job can be completed by multiple workers. If three workers each complete a job worth $1, the total profit is $3.

4. Zero Profit: If a worker cannot complete any available job (all jobs are too difficult), they contribute $0 to the total profit.

Your task is to assign workers to jobs in a way that maximizes the total profit. Each worker should be assigned to the most profitable job they are capable of completing.

For example, if you have:

• Jobs with difficulty = [2, 4, 6] and profit = [10, 20, 30]
• Workers with abilities [4, 5, 3]

The optimal assignment would be:

• Worker with ability 4 → job with difficulty 4 (profit 20)
• Worker with ability 5 → job with difficulty 4 (profit 20)
• Worker with ability 3 → job with difficulty 2 (profit 10)
• Total profit = 50

Intuition

The key insight is that each worker should take the most profitable job they're capable of doing. Since multiple workers can do the same job, we don't need to worry about "reserving" jobs for specific workers.

Think of it this way: if a worker can handle difficulty level 5, they can do any job with difficulty ≤ 5. Among all these jobs they're capable of doing, why would they choose anything other than the one with maximum profit?

This leads us to a greedy approach: for each worker, find the highest-paying job within their capability.

To implement this efficiently, we can:

1. Sort the jobs by difficulty: This allows us to quickly find all jobs a worker can do (all jobs up to a certain difficulty threshold).

2. Sort the workers by ability: This lets us process workers in order, and reuse our progress. If worker A has ability 3 and we've already found the best job for them, when we move to worker B with ability 5, we know they can do everything worker A can do, plus potentially more difficult jobs.

3. Use two pointers: As we process each worker in ascending order of ability, we can maintain a pointer in the jobs array. For each worker, we advance this pointer to include all new jobs they can handle, keeping track of the maximum profit seen so far.

The beauty of this approach is that once we've found the maximum profit available for jobs with difficulty ≤ k, we can reuse this information for any worker with ability ≥ k. This avoids redundant searching and gives us an efficient O(n log n + m log m) solution where n is the number of jobs and m is the number of workers.

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

Solution Approach

Let's walk through the implementation step by step:

Step 1: Sort the workers and create job pairs

worker.sort()
jobs = sorted(zip(difficulty, profit))

• We sort the worker array in ascending order of ability
• We combine difficulty and profit into pairs and sort them by difficulty. This creates a list of tuples like [(difficulty1, profit1), (difficulty2, profit2), ...] sorted by the first element (difficulty)

Step 2: Initialize tracking variables

ans = mx = i = 0

• ans: accumulates the total profit
• mx: tracks the maximum profit available for jobs we've seen so far
• i: pointer to track our position in the sorted jobs array

Step 3: Process each worker using two pointers

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

For each worker with ability w:

• We advance pointer i through the jobs array, considering all jobs where jobs[i][0] <= w (difficulty ≤ worker's ability)
• For each new job this worker can handle, we update mx to track the maximum profit seen: mx = max(mx, jobs[i][1])
• After checking all newly accessible jobs, we add mx to our answer - this worker takes the best job available to them
• Importantly, we don't reset i for the next worker. Since workers are sorted by ability, the next worker can do everything the current worker can do, plus potentially more

Why this works:

• Since both arrays are sorted, when we move from a worker with ability k to one with ability k+1, we only need to check the additional jobs that become available (those with difficulty between k and k+1)
• The variable mx maintains the best profit among all jobs with difficulty ≤ current worker's ability
• Each worker gets assigned the job with maximum profit they can handle (stored in mx)

Time Complexity: O(n log n + m log m) for sorting, plus O(n + m) for the two-pointer traversal Space Complexity: O(n) for the jobs array

Example Walkthrough

Let's work through a concrete example to illustrate the solution approach.

Given:

• difficulty = [5, 2, 4, 6, 8]
• profit = [10, 15, 30, 25, 40]
• worker = [4, 7, 3, 6]

Step 1: Sort workers and create job pairs

After sorting:

• worker = [3, 4, 6, 7] (sorted by ability)
• jobs = [(2, 15), (4, 30), (5, 10), (6, 25), (8, 40)] (sorted by difficulty)

Step 2: Initialize variables

• ans = 0 (total profit)
• mx = 0 (max profit seen so far)
• i = 0 (pointer in jobs array)

Step 3: Process each worker

Worker 1 (ability = 3):

• Check jobs where difficulty ≤ 3
• jobs[0] = (2, 15): difficulty 2 ≤ 3 ✓
  • Update mx = max(0, 15) = 15
  • Move i to 1
• jobs[1] = (4, 30): difficulty 4 > 3 ✗ (stop)
• Add mx = 15 to answer
• ans = 15, i = 1, mx = 15

Worker 2 (ability = 4):

• Continue from where we left off (i = 1)
• Check additional jobs where difficulty ≤ 4
• jobs[1] = (4, 30): difficulty 4 ≤ 4 ✓
  • Update mx = max(15, 30) = 30
  • Move i to 2
• jobs[2] = (5, 10): difficulty 5 > 4 ✗ (stop)
• Add mx = 30 to answer
• ans = 45, i = 2, mx = 30

Worker 3 (ability = 6):

• Continue from i = 2
• Check additional jobs where difficulty ≤ 6
• jobs[2] = (5, 10): difficulty 5 ≤ 6 ✓
  • Update mx = max(30, 10) = 30 (no change)
  • Move i to 3
• jobs[3] = (6, 25): difficulty 6 ≤ 6 ✓
  • Update mx = max(30, 25) = 30 (no change)
  • Move i to 4
• jobs[4] = (8, 40): difficulty 8 > 6 ✗ (stop)
• Add mx = 30 to answer
• ans = 75, i = 4, mx = 30

Worker 4 (ability = 7):

• Continue from i = 4
• Check additional jobs where difficulty ≤ 7
• i = 4 is already at the end of jobs array (no more jobs to check)
• The best job this worker can do is still the one with profit 30
• Add mx = 30 to answer
• ans = 105

Final Result: 105

Each worker was assigned to their optimal job:

• Worker (ability 3) → Job (difficulty 2, profit 15)
• Worker (ability 4) → Job (difficulty 4, profit 30)
• Worker (ability 6) → Job (difficulty 4, profit 30)
• Worker (ability 7) → Job (difficulty 4, profit 30)

Notice how the two-pointer technique allows us to efficiently find the best job for each worker without repeatedly searching through all jobs. The key insight is that once we've identified the maximum profit for jobs up to a certain difficulty, we can reuse this information for all subsequent workers with higher abilities.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n + m × log m)

The time complexity breaks down as follows:

• Sorting the worker array takes O(m × log m) where m is the length of the worker array
• Creating and sorting the jobs list (zipping difficulty and profit, then sorting) takes O(n × log n) where n is the length of the difficulty/profit arrays
• The main loop iterates through each worker (m iterations), and the inner while loop moves through jobs. Although there's a nested loop structure, the index i only moves forward and never resets, so each job is visited at most once across all iterations. This contributes O(n + m) to the complexity
• The dominant operations are the sorting steps, giving us a total time complexity of O(n × log n + m × log m)

Space Complexity: O(n)

The space complexity analysis:

• The jobs list stores a sorted version of zipped difficulty and profit pairs, requiring O(n) space where n is the number of jobs
• The sorting of worker is done in-place (Python's sort modifies the list directly), so no additional space is needed for that operation
• Other variables (ans, mx, i, w) use constant space O(1)
• Therefore, the total space complexity is O(n)

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

Common Pitfalls

Pitfall 1: Forgetting that multiple workers can do the same job

The Mistake: A common misconception is thinking each job can only be assigned once, leading to incorrect solutions that try to match workers to unique jobs like a bipartite matching problem.

Why it happens: Many assignment problems have a one-to-one constraint, so it's natural to assume the same here.

Example that breaks:

• Jobs: difficulty = [1], profit = [100]
• Workers: [5, 5, 5]
• Wrong answer: 100 (thinking only one worker can take the job)
• Correct answer: 300 (all three workers can do the same job)

Solution: Remember that jobs are reusable - track the maximum profit available at each difficulty level, not which specific jobs are "taken."

Pitfall 2: Not considering that a harder job might have less profit

The Mistake: Assuming that higher difficulty always means higher profit and just assigning each worker the hardest job they can do.

Why it happens: It seems intuitive that harder jobs would pay more.

Example that breaks:

• Jobs: difficulty = [2, 5], profit = [50, 10]
• Worker with ability 5
• Wrong answer: 10 (taking the hardest job)
• Correct answer: 50 (taking the easier but more profitable job)

Solution: Always track the maximum profit among ALL jobs a worker can handle, not just the hardest one. This is why the code maintains max_profit_so_far across all feasible difficulties.

Pitfall 3: Resetting the job index for each worker

The Mistake: Setting job_index = 0 for each worker, causing unnecessary re-scanning of the jobs array.

Why it happens: It seems like each worker needs to check all possible jobs from the beginning.

Example of inefficiency:

for worker_ability in worker:
    job_index = 0  # WRONG: This resets for each worker
    while job_index < len(jobs) and jobs[job_index][0] <= worker_ability:
        # ... process jobs

Solution: Keep the job index persistent across workers. Since workers are sorted by ability, each subsequent worker can do everything the previous worker could do, plus potentially more. The two-pointer technique leverages this monotonic property for O(n + m) traversal instead of O(n * m).