AlgoMaster Logo

Most Profit Assigning Work

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to assign jobs to workers to maximize total profit. Each worker has an ability level, and they can only do jobs whose difficulty is at most their ability. A worker can be assigned at most one job, but the same job can be given to multiple workers. So if the best-paying job that a worker can handle pays 50, every worker who can handle it should take that job.

Because the same job can go to multiple workers, there is no competition between workers for jobs. Each worker's choice is independent: find the single most profitable job that worker can do, and the answer is the sum of those best choices.

Higher difficulty does not always mean higher profit. A job with difficulty 6 might pay more than a job with difficulty 8. We cannot match workers to jobs by difficulty alone. We need the maximum profit available among all jobs at or below each difficulty level.

Key Constraints:

  • 1 <= n, m <= 10^4 → A nested loop over workers and jobs is up to 10^8 operations in the worst case, borderline for the time limit. Sorting-based methods at O(n log n + m log n) or O(n log n + m log m) are well within budget.
  • 1 <= difficulty[i], profit[i], worker[j] <= 10^5 → Difficulties are bounded by 100,000, which leaves room for a prefix-max array indexed by difficulty if we wanted an O(max_difficulty + m) approach. The total profit is at most m times the largest profit, 10^4 10^5 = 10^9, which fits in a signed 32-bit integer (limit about 2.1 10^9), so a plain int accumulator does not overflow.

Approach 1: Brute Force

Intuition

For each worker, scan through every job and keep the most profitable one whose difficulty is at most the worker's ability. Because there is no competition between workers for jobs, this per-worker best is exactly that worker's contribution to the total.

This does redundant work. If two workers have the same ability, we scan all jobs twice and compute the same answer both times.

Algorithm

  1. Initialize totalProfit = 0.
  2. For each worker j:
    • Initialize bestProfit = 0.
    • For each job i:
      • If difficulty[i] <= worker[j] and profit[i] > bestProfit, update bestProfit = profit[i].
    • Add bestProfit to totalProfit.
  3. Return totalProfit.

Visualization and Code

Loading animation...

The rescanning is the bottleneck. The next approach sorts the jobs by difficulty once and precomputes the best profit available up to each difficulty, turning each worker's lookup into a single binary search.

Approach 2: Sort + Binary Search

Intuition

Preprocessing removes the repeated work. Sort the jobs by difficulty, then build a prefix maximum array of profits. After sorting, maxProfit[i] holds the highest profit among jobs at indices 0 through i. Because the jobs are sorted by difficulty, that value is the best profit reachable with difficulty at most jobs[i].difficulty.

For each worker, binary search for the rightmost job whose difficulty is at most the worker's ability. The prefix maximum at that position is the worker's best profit.

Algorithm

  1. Pair up each job's difficulty and profit, then sort these pairs by difficulty.
  2. Build a prefix maximum array: for each position i, maxProfit[i] = max(maxProfit[i-1], profit[i]).
  3. For each worker:
    • Binary search for the largest difficulty that is at most the worker's ability.
    • If such a job exists, add maxProfit[index] to the total.
  4. Return the total profit.

Visualization and Code

Loading animation...

Each binary search still re-discovers which jobs are reachable from scratch. The next approach sorts the workers too, so a single forward sweep over the jobs serves every worker.

Approach 3: Sort Both + Two Pointers (Optimal)

Intuition

Sort both the jobs and the workers. Processing workers from weakest to strongest means the set of reachable jobs only grows. Keep one pointer into the sorted jobs list and a running maximum profit. For each worker, advance the pointer to include every newly reachable job, updating the running maximum as you go, then add that maximum to the total.

The job pointer only moves forward and never resets, so the combined sweep over all workers touches each job once. After the two sorts, the processing is linear in n + m.

Algorithm

  1. Pair up each job's difficulty and profit, then sort by difficulty.
  2. Sort the worker array in ascending order.
  3. Initialize jobIndex = 0 and bestProfit = 0.
  4. For each worker (in sorted order):
    • While jobIndex < n and jobs[jobIndex].difficulty <= worker's ability:
      • Update bestProfit = max(bestProfit, jobs[jobIndex].profit).
      • Increment jobIndex.
    • Add bestProfit to totalProfit.
  5. Return totalProfit.

Visualization and Code

Loading animation...