On this page
Description
Children with greed factors and cookies of different sizes, people and two-seat boats, tasks and workers of different skill: each asks how many pairs can be matched, and trying every matching is exponential. After sorting, one simple rule is provably optimal. Knowing why it's optimal is what tells you when a similar-looking rule isn't. This skill covers the two sorted sweeps and the exchange argument that proves them.
We'll go from simple to more technical:
- The pattern: sort both sides and give each child the smallest cookie that satisfies them.
- A second flavor: pair the heaviest with the lightest (boats).
- Where threshold matching shows up (resource allocation, scheduling, packing).
- What breaks it: one-sided sorting, boundary comparisons, neighbor pairing, other objectives.
The approach
Java
int findContentChildren(int[] greed, int[] cookies) {
Arrays.sort(greed);
Arrays.sort(cookies);
int child = 0;
for (int c = 0; child < greed.length && c < cookies.length; c++) {
if (cookies[c] >= greed[child]) child++; // smallest cookie that contents the least greedy child
// otherwise this cookie is too small for every remaining child: skip it
}
return child;
}
Python
def find_content_children(greed: list[int], cookies: list[int]) -> int:
greed = sorted(greed)
child = 0
for c in sorted(cookies):
if child == len(greed):
break
if c >= greed[child]:
child += 1 # smallest cookie that contents the least greedy child
# otherwise this cookie is too small for every remaining child: skip it
return child
Two facts make the sweep correct. A cookie too small for the least greedy remaining child is too small for all of them, so discarding it loses nothing. And giving the least greedy child the smallest cookie that satisfies them is safe - an exchange argument: in any optimal matching, swap that cookie in for whatever the child got; the bigger cookie that's freed can only content more children, never fewer. Both sides must be sorted; with unsorted cookies, a large cookie can be used up on an easy child that a smaller cookie would have contented.
A second flavor: pair from both ends
Boats carry at most two people with total weight at most limit. Sort once and pair the heaviest remaining person with the lightest:
Java
int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int boats = 0;
for (int light = 0, heavy = people.length - 1; light <= heavy; heavy--) {
if (people[light] + people[heavy] <= limit) light++; // the lightest rides along if it fits
boats++; // the heaviest leaves now either way
}
return boats;
}
Python
def num_rescue_boats(people: list[int], limit: int) -> int:
people = sorted(people)
boats = 0
light, heavy = 0, len(people) - 1
while light <= heavy:
if people[light] + people[heavy] <= limit:
light += 1 # the lightest rides along if it fits
heavy -= 1
boats += 1 # the heaviest leaves now either way
return boats
The heaviest person needs a boat no matter what. If anyone can share it, the lightest can, and choosing the lightest keeps every heavier person available for someone else. Pairing neighbors in sorted order looks similar but fails: weights [1, 2, 4, 5] with limit 6 give (1, 2), then 4 and 5 alone - 3 boats - while (1, 5) and (2, 4) need only 2.
Where you'll see it
Assigning tasks to workers by minimum required skill (use the least-skilled worker who qualifies, saving experts for hard tasks), packing two jobs per machine under a memory limit, and seating groups at tables of fixed size all use sorted matching.
Which tool for which job?
| You need | Use |
|---|---|
| Max matches when bigger always works for more | sort both sides, smallest that fits |
| Pairs under a weight limit | sort, then heaviest with lightest |
| Arbitrary compatibility ("A works with B and C") | bipartite matching with augmenting paths |
| Different rewards per match | weighted assignment (Hungarian algorithm), not a count greedy |
| More than two per boat | bin packing: greedy isn't optimal |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Sorting only one side | the exchange argument fails | sort both |
> instead of >= | exact fits rejected | match the problem's rule |
| Pairing neighbors | [1, 2, 4, 5], limit 6: 3 boats instead of 2 | heaviest with lightest |
| First-fit on arbitrary compatibility | 1 match where 2 are possible | augmenting paths |
| Count greedy with rewards | earns 1 instead of 10 | weighted assignment |
| The two-person rule with three seats | 3 boats where 2 suffice | search or DP; it's bin packing |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why is it safe to throw away a cookie that can't content the least greedy remaining child?
Show answer
Every remaining child is at least as greedy as that child, so the cookie can't content any of them. Discarding it can't cost a match.
2. Why does the boat solution pair the heaviest person with the lightest rather than the next heaviest?
Show answer
The heaviest needs a boat regardless. If anyone fits with them, the lightest does, and taking the lightest leaves every heavier person free to pair elsewhere. Pairing neighbors can waste capacity: [1, 2, 4, 5], limit 6 needs 3 boats that way but 2 with (1, 5) and (2, 4).
3. What is an exchange argument?
Show answer
A proof that a greedy choice is safe: take any optimal solution, replace its choice with the greedy one, and show the result is still valid and no worse. Repeating the argument for each step shows the whole greedy solution is optimal.
Key takeaways
- Sort both sides, then give the smallest sufficient resource to the least demanding request.
- A resource too small for the smallest request is useless - skip it.
- Two per container: pair the heaviest with the lightest, not with a neighbor.
- Prove greedy rules with an exchange argument; they hold only for the objective they were proved for.