Most Profit Assigning Work

Most Profit Assigning Work

What is this problem about?

The Most Profit Assigning Work problem gives you a list of jobs (each with a difficulty and profit) and a list of workers (each with a maximum ability level). Each worker can complete any job with difficulty ≤ their ability, and earns the job's profit. A job can be assigned to multiple workers. Maximize the total profit across all workers. This Most Profit Assigning Work coding problem is solved elegantly with sorting and greedy matching.

Why is this asked in interviews?

NetEase, Microsoft, Meta, Amazon, TikTok, and Google ask this because it tests the ability to match workers to the best possible job using sorting and a two-pointer or binary search approach. The array, sorting, two pointers, binary search, and greedy interview pattern is fully represented. The key insight — precomputing the best profit up to each difficulty level — separates clean solutions from brute-force ones.

Algorithmic pattern used

Sort both + prefix max + two pointers or binary search. Sort jobs by difficulty. Build a prefix max array of profits (best profit achievable for difficulty ≤ i). Sort workers by ability. For each worker (in ascending ability order), advance through jobs using a pointer and track the maximum profit seen so far. Each worker earns the maximum profit of all jobs they can handle.

Example explanation

Jobs: [(2,100),(1,200),(3,300)]. Workers: [3,1,2]. Sort jobs by difficulty: [(1,200),(2,100),(3,300)]. Prefix max profits: [200,200,300]. Sort workers: [1,2,3].

• Worker ability=1: max profit up to difficulty 1 = 200. Total = 200.
• Worker ability=2: max profit up to difficulty 2 = 200. Total = 400.
• Worker ability=3: max profit up to difficulty 3 = 300. Total = 700.

Common mistakes candidates make

• Assigning each job only once (jobs can be assigned to multiple workers).
• Not building a prefix max (the best job for difficulty ≤ d, not exactly d).
• Not sorting workers before the two-pointer sweep.
• Using binary search without the prefix max (returns exact difficulty match, not best).

Interview preparation tip

"Assign best matching resource to each query" problems always benefit from sorting both lists and using a two-pointer sweep with a running maximum. The prefix max pattern — best[i] = max(best[i-1], profit[i]) — converts "best up to difficulty d" from O(d) to O(1). This pattern generalizes to any problem where you want the best item satisfying a threshold, after sorting. Practice it with "assign tasks to workers" variants using different constraints.