Each child has an appetite need[i], and each snack has a size snacks[j]. A child is happy if they get one snack whose size is at least their appetite. Each snack can go to at most one child, and each child gets at most one snack.
Write max_happy(need: list[int], snacks: list[int]) -> int that returns the largest number of children you can make happy.
max_happy([1, 2, 3], [1, 1]) # 1 (only the child with need 1 can be fed)
max_happy([4, 1, 2], [3, 1, 5]) # 3 (1 gets 1, 2 gets 3, 4 gets 5)
max_happy([5], []) # 0
Constraints: up to 10^5 children and 10^5 snacks, sizes between 1 and 10^9. Your answer should be O(n log n).
Show hint
sort both lists and walk them with two pointers, giving each child (smallest appetite first) the smallest snack that is big enough; a snack too small for this child is too small for every later child, so skip it.