Coat Drive Handout
A winter coat drive has a pile of donated coats. Each coat has a warmth rating printed on its tag. A line of people is waiting, and each person tells you the lowest warmth rating that would keep them warm enough.
A person is happy with any coat rated at least their number. Each coat can go to one person, and each person takes at most one coat. You want as many people as possible to walk away warm.
Your task
Write maxWarmPeople(needs, coats). needs[i] is the lowest warmth person i accepts. coats[j] is the warmth of coat j. Return the largest number of people who can each get a coat with coats[j] ≥ needs[i].
Either list may be empty; then the answer is 0. Neither list is sorted.
maxWarmPeople(needs: int[], coats: int[]) → int
Examples
needs = [3, 6, 4] coats = [2, 5, 4]
2
The coat rated 2 is too thin for everyone. The 4 fits the person who needs 3 (or the one who needs 4), and the 5 fits the other one. The person who needs 6 cannot be helped by any coat. So 2 people get coats.
needs = [2, 7] coats = [8, 2]
2
If you hand the first coat that fits to the first person, the person needing 2 takes the 8 and the person needing 7 gets nothing. Give the 2 to the person needing 2 and the 8 to the person needing 7, and both are warm.
Constraints
- 0 ≤ needs.length ≤ 10,000
- 0 ≤ coats.length ≤ 10,000
- 1 ≤ needs[i], coats[j] ≤ 1,000
Start with brute force
Try every way of handing out coats: for each person, try each unused coat that fits, or no coat, and keep the best total. That is a search over all matchings, and the number of matchings explodes: with even 20 people and 20 coats it is far beyond what any computer can try.
A gentler-looking first idea is to go down the line and give each person the first coat in the pile that fits. It is fast, but it is wrong: the second example shows a needy person losing out because a warm coat went to someone who needed very little.
Hints
0 of 4 shown- Hint 1
In the second example, the person who needs 2 could take either coat. Which coat should they take, so that you lose as little as possible?
- Hint 2
A coat that is warmer than needed is wasted warmth. When a person can be served, serve them with the thinnest coat that still works. Save the warm coats for people who need them.
- Hint 3
Sort both lists. Now think about the thinnest coat. If it is not warm enough for the least needy person, can it be warm enough for anyone?
- Hint 4
Sort needs and coats. Walk through the coats from thinnest to warmest with a pointer into the sorted needs. If the current coat covers the current least needy person, that person is served and the pointer moves on. Otherwise the coat is useless, so skip it. The pointer's final position is the answer.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The greedy rule: give each coat to the least needy person it can serve, starting from the thinnest coat. A thin coat has the fewest possible owners, so use it on the easiest person to please. Warm coats stay free for needy people.
Trace the first example. Sorted needs: [3, 4, 6]. Sorted coats: [2, 4, 5].
- Coat 2. The least needy person wants 3. 2 < 3, so this coat fits nobody. Skip it.
- Coat 4. Least needy still waiting wants 3. 4 ≥ 3, so they take it. Served: 1.
- Coat 5. Next person wants 4. 5 ≥ 4, so they take it. Served: 2.
- No coats left. The person needing 6 goes without. Answer: 2.
Why skipping a coat is safe: if a coat cannot cover the least needy person left, it cannot cover anyone left, because everyone else needs at least as much.
function maxWarmPeople(needs, coats) {
const people = [...needs].sort((a, b) => a - b);
const pile = [...coats].sort((a, b) => a - b);
let served = 0; // index of the least needy person still waiting
for (const coat of pile) {
if (served < people.length && coat >= people[served]) {
served++; // thinnest coat that works goes to this person
}
// otherwise this coat is too thin for everyone left: skip it
}
return served;
}def max_warm_people(needs, coats):
people = sorted(needs)
pile = sorted(coats)
served = 0 # index of the least needy person still waiting
for coat in pile:
if served < len(people) and coat >= people[served]:
served += 1 # thinnest coat that works goes to this person
# otherwise this coat is too thin for everyone left: skip it
return servedRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.