826. Most Profit Assigning Work - Detailed Explanation

Problem Statement

You have two integer arrays:

difficulty[i] and profit[i] describe the difficulty and profit of job i.
worker[j] is the ability of worker j (the maximum difficulty they can handle).

Each worker can be assigned at most one job whose difficulty is ≤ their ability, earning the corresponding profit (or 0 if no job is possible). Return the sum of the maximum profit each worker can earn.

Examples

Example 1

Input  
  difficulty = [2,4,6,8,10]  
  profit     = [10,20,30,40,50]  
  worker     = [4,5,6,7]  
Output 100  
Explanation  
  Worker abilities → [4,5,6,7]  
  Best jobs per worker:  
    4 → difficulty≤4 gives max profit 20  
    5 → difficulty≤5 gives max profit 20  
    6 → difficulty≤6 gives max profit 30  
    7 → difficulty≤7 gives max profit 30  
  Sum = 20+20+30+30 = 100

Example 2

Input  
  difficulty = [85,47,57]  
  profit     = [24,66,99]  
  worker     = [40,25,25]  
Output   0  
Explanation  
  No worker can do any of the listed jobs → earns 0 each → sum = 0

Constraints

1 ≤ difficulty.length == profit.length ≤ 10^5
1 ≤ worker.length ≤ 10^5
1 ≤ difficulty[i], profit[i], worker[j] ≤ 10^9

Hints

For a single worker, how would you pick the best job in O(#jobs)?
Can you preprocess the jobs so that querying the best profit for any ability takes less than O(#jobs)?
Which data structure or algorithm lets you quickly find “the largest difficulty ≤ ability”?

Approach 1 – Brute Force

Idea

For each worker, scan all jobs and pick the max profit among those with difficulty ≤ ability.

Steps

Initialize total = 0.
For each w in worker:
- Let best = 0.
- For each job i: if difficulty[i] ≤ w, best = max(best, profit[i]).
- Add best to total.
Return total.

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time O(W × J) where W=number of workers, J=number of jobs
Space O(1) extra

Approach 2 – Sort + Prefix Max + Binary Search

Idea

Pair each job (difficulty[i], profit[i]) and sort by difficulty.
Build an array maxProfitUpTo[i] which is the maximum profit among jobs 0…i.
For each worker ability w, binary‐search the rightmost job with difficulty ≤ w, then add maxProfitUpTo[idx] (or 0 if none).

Steps

Create jobs = [(d,p) for d,p in zip(difficulty,profit)] and sort by d.

Build maxProfitUpTo where

maxProfitUpTo[0] = jobs[0].profit  
for i in 1…n-1:  
  maxProfitUpTo[i] = max(maxProfitUpTo[i-1], jobs[i].profit)

For each w in worker:
- Binary‐search jobs for the largest index i with jobs[i].difficulty ≤ w.
- If found, add maxProfitUpTo[i] to total.
Return total.

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Sorting jobs: O(J log J)
Building prefix max: O(J)
For W workers: each binary‐search O(log J) → O(W log J)
Total: O((J+W) log J)

Approach 3 – Two‑Pointer One‑Pass (O(J log J + W log W + J + W))

Idea

Sort both jobs and worker. Sweep through workers in increasing ability, advancing a pointer over the jobs to maintain the best profit so far.

Steps

Sort jobs by difficulty; sort worker abilities.
Initialize best = 0, total = 0, i = 0 (job pointer).
For each w in sorted worker:
- While i < J and jobs[i].difficulty ≤ w:
  best = max(best, jobs[i].profit); i++.
- Add best to total.
Return total.

(Track original worker order only if you need per‐worker results; for sum it doesn’t matter.)

Step‑by‑Step Walkthrough

Using difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]:

jobs sorted = [(2,10),(4,20),(6,30),(8,40),(10,50)]
worker sorted = [4,5,6,7]
Start i=0,best=0,total=0
- w=4: advance i over (2,10) → best=10; (4,20)→best=20; stop at (6,30). → total+=20
- w=5: no new jobs (next difficulty=6>5) → total+=20 (best stays 20)
- w=6: advance (6,30) → best=30; stop. → total+=30
- w=7: no new jobs → total+=30
Sum = 20+20+30+30 = 100

Common Mistakes

Not building the prefix max over profits before binary search → you might pick a lower‐profit job with higher difficulty.
Off‑by‑one in binary search index adjustments.
Forgetting to sort both lists in the two‑pointer approach.

Edge Cases

No job has difficulty ≤ any worker → all earn 0.
Identical difficulties with different profits → prefix max handles it.
Large values up to 10^9 → watch out for integer overflow when summing many profits (use 64‑bit if needed).