Loading...
Loading...
Loading...
The NSS unit of a college visits a primary school with a box of cookies. There are n children, and child i is happy only with a cookie of size at least g[i]. There are m cookies, and cookie j has size s[j].
Each child can get at most one cookie, and each cookie can go to at most one child. Print the largest number of children who can be made happy.
Example 1
Input
3 1 2 3 2 1 1
Output
1
Both cookies have size 1. Only the child who wants size 1 can be happy, so the answer is 1.
Example 2
Input
3 1 2 4 4 1 3 2 2
Output
2
Give size 1 to the first child and size 2 to the second. No cookie is big enough for the child who wants 4.
Try the problem first. Open one hint at a time.
A child who wants a small cookie is the easiest to please. Who should get the smallest cookie?
Sort both lists. Then try the smallest cookies on the children who want the least.
Walk through the cookies in sorted order with one index for the children. If the cookie fits the current child, that child is happy and you move to the next child.
Move to the next cookie every time, whether it was used or was too small.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor