Snacks for the Field Trip
EasyGreedyFree
Problem
A teacher packs snacks for a field trip. Child i is only happy with a snack of size at least appetites[i]; snack j has size snacks[j].
Each child receives at most one snack and each snack goes to at most one child. Return the largest number of children that can be made happy.
Example 1
- Input:
- appetites = [4, 2, 7], snacks = [3, 8, 1, 5]
- Output:
- 3
Give 3 to the child who needs 2, 5 to the one who needs 4 and 8 to the one who needs 7. The snack of size 1 is left over.
Example 2
- Input:
- appetites = [1, 2, 3], snacks = [1, 1]
- Output:
- 1
Both snacks have size 1, and only the child with appetite 1 can be satisfied by either.
Constraints
- 1 ≤ appetites.length ≤ 3 · 10^4
- 0 ≤ snacks.length ≤ 3 · 10^4
- 1 ≤ appetites[i], snacks[j] ≤ 2^31 - 1
Hint
Show the first hint
Which child is the easiest to please, and which snack is the least valuable to spend on them?
Walkthrough
How to approach it
01Clarify before coding
- Can a child receive two small snacks that add up? No: one snack per child, and size must be at least the appetite on its own.
- Can there be more snacks than children, or none at all? Yes to both; with no snacks the answer is 0.
- Do we need the actual assignment? No, only the count.
02Brute force
Try every way of assigning snacks to children (a bipartite matching search) and keep the assignment with the most happy children.
Cost: Exponential with plain backtracking; even a general bipartite matching algorithm is O(V·E), up to ~10^13 edge checks here. Far too slow and far too heavy for a problem with a one-dimensional order.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.