513. Most Profit Assigning Work
You are staffing a gig platform. There are n gigs: gig i has a difficulty rating difficulty[i] and pays profit[i]. There are also m workers, where worker[j] is the skill level of worker j.
A worker may take at most one gig, and only a gig whose difficulty does not exceed their skill. The same gig may be handed out to any number of workers — nobody blocks anybody.
Your function receives the arrays difficulty, profit, and worker, and must return the largest total payout achievable when every worker picks optimally. A worker who cannot handle any gig simply earns 0.
Example 1:
Input: difficulty = [2, 4, 6, 8, 10], profit = [10, 20, 30, 40, 50], worker = [4, 5, 6, 7]
Output: 100
Explanation: Workers with skills 4 and 5 take the difficulty-4 gig (20 each); workers with skills 6 and 7 take the difficulty-6 gig (30 each). 20 + 20 + 30 + 30 = 100.
Example 2:
Input: difficulty = [85, 47, 57], profit = [24, 66, 99], worker = [40, 25, 25]
Output: 0
Explanation: The easiest gig has difficulty 47, but the strongest worker only has skill 40 — nobody can work, so the payout is 0.
Constraints:
- 1 ≤ difficulty.length == profit.length ≤ 10⁴
- 1 ≤ worker.length ≤ 10⁴
- 1 ≤ difficulty[i], worker[j] ≤ 10⁵
- 1 ≤ profit[i] ≤ 10⁴
Hints:
Workers never compete: each one independently earns the single best profit among gigs with difficulty ≤ their skill. So solve one worker at a time.
Careful — a harder gig is not guaranteed to pay more. Sort gigs by difficulty and precompute a running maximum: bestUpTo[k] = the best profit among the first k+1 gigs. Then each worker is one binary search.
Sort the workers too. As skill only increases, the set of feasible gigs only grows, so one pointer can sweep the sorted gigs once while carrying the running best — no binary search needed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: difficulty = [2, 4, 6, 8, 10], profit = [10, 20, 30, 40, 50], worker = [4, 5, 6, 7]
Expected output: 100