1086. The Best Job Each Worker Can Do

m jobs are given, each with a DIFFICULTY and a PROFIT. k workers are given, each with an ABILITY. A worker can do a job when their ability is at least its difficulty, and a job may be done by any number of workers, each earning its full profit. A worker who can do nothing earns 0.

Print the largest total profit, assuming every worker takes the best-paying job they are able to do.

jobs (2,10) (4,20) (6,30) (8,40), abilities 4 5 6 7 -> 100 jobs (85,47) (57,4) (61,15), abilities 90 96 4 -> 94 jobs (5,100), abilities 4 -> 0

For the second row, the workers of ability 90 and 96 both take the job of difficulty 85 for 47 each, and the worker of ability 4 can do nothing.

## What most people try first

For each worker, scan every job: O(m k), which is 10^10 at the limits and is the brute force this problem was checked against.

Sorting the jobs by profit descending and, for each worker, taking the first affordable one, is also O(m k) in the worst case and no better.

## Sort both sides and sweep once

The key observation is that jobs are NOT exclusive. So a worker of ability w earns

best(w) = the largest profit among all jobs with difficulty <= w

and that is a non-decreasing function of w: a stronger worker can do everything a weaker one can. So sort the workers ascending and walk the jobs forward without ever going back.

sort the jobs by difficulty ascending sort the workers ascending i = 0, best = 0, total = 0 for each worker w in ascending order: while i < m and difficulty[i] <= w: best = max(best, profit[i]); i += 1 total += best

## Why a running maximum is enough, and why it never resets

best holds the largest profit among all jobs already absorbed, and a job is absorbed exactly when its difficulty is at most the current worker's ability. Since the workers only get stronger, no absorbed job ever becomes unavailable, so best never has to fall. That is why i never rewinds and the sweep is linear after the sorts.

Note that the highest-profit affordable job is NOT usually the hardest affordable one. Sorting by difficulty and taking the LAST affordable job answers 15 for the second sample instead of 47, because a harder job can pay less. The running maximum is what fixes it.

## Why sorting the workers matters

Without it, i would have to rewind for every weaker worker and the sweep collapses back to O(m k). Since each worker's earnings do not depend on any other worker, reordering them is free.

## Where this sits

Problem #611 also sorts two lists and walks them together, but there each biscuit is consumed by at most one child, so the pointers advance under a different rule. Here nothing is consumed, which is exactly why one running maximum replaces the whole matching.

## Overflow

k reaches 100000 and a profit reaches 10^9, so the total reaches 10^14. The signed 32 bit limit is 2147483647, and the short test with one job paying 10^9 and three workers totals 3 * 10^9.

## Cost

Time O(m log m + k log k). Space O(m + k).

Constraints - `1 ≤ m ≤ 100000` - `1 ≤ k ≤ 100000` - `1 ≤ difficulty ≤ 1000000000` - `0 ≤ profit ≤ 1000000000` - `0 ≤ ability ≤ 1000000000`