576. Cookie Handout
At a bakery stall, a helper wants to hand out free cookies to a queue of children. Child i will only be happy with a cookie whose size is at least greed[i]. The tray holds cookies whose sizes are listed in cookies. Each cookie can be given to at most one child, and each child can receive at most one cookie.
Return the largest number of children who can be made happy at the same time. A child who receives a cookie that is too small, or no cookie at all, is simply not counted. The arrays are in no particular order.
An O(n log n) solution that sorts both lists and walks them together with two pointers is expected, using O(1) extra space beyond the sorted copies.
Example 1
- Input:
- greed = [4,1,3], cookies = [2,5]
- Output:
- 2
- Explanation:
Give the size-2 cookie to the child needing 1 and the size-5 cookie to the child needing 3, making 2 children happy.
Example 2
- Input:
- greed = [5,6], cookies = [1,2,3]
- Output:
- 0
- Explanation:
Every cookie is smaller than every demand, so nobody is happy.
Example 3
- Input:
- greed = [1,1,1], cookies = [1,1,1,1,1]
- Output:
- 3
- Explanation:
Three equal-sized cookies are enough for the three children, leaving two spare.
Constraints
1 ≤ greed.length ≤ 300001 ≤ cookies.length ≤ 300001 ≤ greed[i], cookies[j] ≤ 1000000000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n + m log m)
- Space
- O(1)