770. Handing Out the Energy Pills

There are n tasks and m workers. Task j needs strength t[j]; worker i has strength w[i]. A worker may be given at most one task and a task may be given to at most one worker, and worker i can complete task j only when their strength is at least t[j].

You also hold pills energy pills. A pill given to a worker raises that worker's strength by strength for the whole assignment. A worker may take at most one pill, and a pill is wasted if the worker is given no task.

Print the largest number of tasks that can be completed.

t = 3 2 1, w = 0 3 3, pills = 1, strength = 1 answer 3 t = 5 5 5, w = 0 0 0, pills = 1, strength = 1 answer 0 t = 1 1 1 1, w = 10 10, pills = 0, strength = 0 answer 2 t = 10 5 5 5, w = 5 5 5 5, pills = 1, strength = 5 answer 4

## Why matching directly is the wrong first move

Sorting both lists and walking them together solves the no-pills version, but pills break it: the decision of whom to dose depends on which tasks you intend to attempt, and which tasks you attempt depends on where the pills went. Trying every subset of dosed workers is exponential.

The way out is to stop asking "how many" and start asking "can I manage exactly k".

## Which k tasks and which k workers

If k tasks can be done at all, they can be the k EASIEST tasks, and they can be done by the k STRONGEST workers.

For the tasks: take any successful set of k tasks and replace its hardest member with any easier task not in the set. The worker who handled the hardest task can certainly handle an easier one, so the assignment survives. Repeat until the set is the k easiest.

For the workers: take any successful assignment using some worker u, and let v be an unused worker with w[v] >= w[u]. Give v the task u had, along with u's pill if there was one. Since v is at least as strong, the task is still within reach. Repeat until the workers used are the k strongest.

So the check only ever looks at a fixed prefix of the sorted tasks and a fixed suffix of the sorted workers, which is why it can be written as a single pass.

## The feasibility sweep

Sort tasks ascending and workers ascending. Consider the chosen workers from WEAKEST to strongest, and keep a deque holding every still-unassigned task that the current worker could do WITH a pill:

feasible(k): dq = empty deque, ptr = 0, left = pills for each of the k strongest workers, weakest first, as W: while ptr < k and t[ptr] <= W + strength: push t[ptr] to the back of dq; ptr += 1 if dq is empty: return false if front(dq) <= W: pop the front # no pill needed else: if left == 0: return false left -= 1; pop the BACK # spend the pill on the hardest reachable task return true

## Why the two pops are the right ones

Work through the weakest worker first, because they are the hardest to place.

If the easiest unassigned reachable task is already within their plain strength, do it without a pill. Nothing is lost: every other worker considered later is at least as strong, so any task this worker could have taken is still available to them, and saving a pill can only help.

If it is not, this worker needs a pill or does nothing. Given that a pill is being spent, spend it on the HARDEST task the boosted worker can reach. Every task in the deque is reachable by this boosted worker; the hardest of them is the one that later, stronger workers are least likely to manage unaided. Formally: let x be the hardest reachable task and y any other in the deque, so y <= x. In any solution where this worker takes y and some later worker takes x, swapping the two tasks keeps both assignments valid, because the later worker is at least as strong and y <= x, and this worker is boosted enough for x by construction. So taking x is never worse.

The deque is exactly right for this: tasks enter in increasing order at the back, the plain branch removes the smallest from the front, and the pill branch removes the largest from the back.

## Why the predicate is monotone

If k tasks can be completed, so can k - 1: drop the hardest chosen task and its worker. So feasibility holds for a prefix 0 .. answer and the answer is the LAST true, which means the midpoint rounds UP.

## The bounds

lo = 0, always achievable. hi = min(n, m), because each task needs its own worker.

## The boundary that breaks a careless implementation

The empty-deque case must return false, not skip the worker. Every one of the k chosen workers has to be given one of the k chosen tasks, because the counts are equal; a worker with nothing reachable means the pairing cannot be completed, even though tasks remain.

The other trap is re-sorting or re-slicing inside the check. The chosen task prefix and worker suffix both change with k, so the pointers must be recomputed per check, but the SORT must not be, or the cost becomes O(n log n log n) with a large constant.

## Relationship with problem 776

776 also searches over a COUNT rather than over a value, and also has to decide whether an assignment of exactly that size exists, there between groups and token kinds with no kind used twice in one group. Both searches round the midpoint UP, because deleting one item from a working assignment always leaves a working one.

The checks are opposite in kind. This one CONSTRUCTS the assignment, weakest worker first, and succeeds when the construction never stalls. 776 cannot afford to construct anything, so it verifies a counting condition over every prefix of the group sizes instead, and its whole trap is that the obvious single count is necessary without being sufficient.

## Overflow

Nothing here overflows a signed 32-bit integer either, and the honest version of this section is shorter than the usual warning. The largest quantity the check computes is W + strength, at most 10^9 + 10^9 = 2 * 10^9, and INT_MAX is 2147483647. Everything else in the sweep is a count or an index bounded by 10^5.

Widen it anyway, out of habit rather than necessity: the margin is about seven percent, and one extra term on that side of the comparison would end it. But widening is not what makes this problem hard. The deque and the choice of which end to pop are.

## Cost

O((n + m) log(n + m)) to sort, then O(k) per check over O(log min(n, m)) checks.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ m ≤ 100000` - `0 ≤ t[j], w[i] ≤ 10^9` - `0 ≤ pills ≤ m` - `0 ≤ strength ≤ 10^9`