611. How Many Children Get a Biscuit
Each child will accept a biscuit only if it is at least as large as their appetite. Each biscuit goes to at most one child, and each child gets at most one biscuit.
Print the largest number of children that can be satisfied.
appetites 1 2 3, biscuits 1 1 -> 1
appetites 1 2, biscuits 1 2 3 -> 2
## Two lists, both sorted, walked once
Sort both. Then walk a pointer along each, never rewinding:
i = 0 (children), j = 0 (biscuits), served = 0
while i < g and j < s:
if biscuit[j] >= appetite[i]:
served += 1
i += 1
j += 1
j advances every step. If the biscuit is big enough it is given away; if it is too small for
the HUNGRIEST-so-far child remaining, it is too small for everyone left, because the children
are sorted too. Either way it is finished with.
## Why the smallest sufficient biscuit
The greedy feeds the least demanding child with the smallest biscuit that will do. The exchange argument is short.
Take an optimal solution. Suppose it satisfies child c at all, where c is the least
demanding child. If it gives c some biscuit b, and the smallest sufficient biscuit b0 is
used elsewhere for child d, swap them: b0 still satisfies c by definition, and b
satisfies d because b >= b0 and b0 satisfied d. The count is unchanged.
If the optimal solution does NOT satisfy c, take whichever biscuit it wasted and give it to
c instead of that child; c is the least demanding, so it fits. The count does not fall.
So there is always an optimal solution that does what the sweep does.
## What this is not
It is tempting to see two sorted lists and reach for a merge. This is not a merge: nothing is
being combined and the two pointers advance under different conditions. Only j is
unconditional.
## Boundaries
More children than biscuits, or the reverse, both work: the loop ends when either list runs out.
Appetites that no biscuit can meet give 0. Equal sizes count, since the rule is "at least as large".
## Cost
Time O(g log g + s log s) for the two sorts. Space O(1) beyond the input.
Constraints - `1 ≤ g ≤ 200000` - `1 ≤ s ≤ 200000` - `1 ≤ each appetite and size ≤ 10^9`
Input
The first line contains two integers g and s, the number of children and biscuits.
The second line contains g integers, the appetites.
The third line contains s integers, the biscuit sizes.
Output
Print one integer, the largest number of children that can be satisfied.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.