455. Assign Cookies #

Problem #

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:You may assume the greed factor is always positive. You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

Problem Summary #

Assume you are an awesome parent and want to give your children some cookies. However, each child can receive at most one cookie. For each child i, there is a greed factor gi, which is the minimum size of a cookie that will satisfy the child’s appetite; and each cookie j has a size sj. If sj >= gi, we can assign cookie j to child i, and the child will be content. Your goal is to satisfy as many children as possible and output this maximum number.

Note: You may assume the greed factor is positive. A child can have at most one cookie.

Solution Idea #

• Suppose you want to give cookies to children, and each child can receive at most one cookie. Each child has a “greed factor”, denoted as g[i], where g[i] represents the minimum cookie size this child needs. At the same time, each cookie has a size value s[i]. If s[j] ≥ g[i], after we give cookie j to child i, the child will be happy. Given arrays g[] and s[], determine how to distribute the cookies so that more children are happy.
• This is a typical simple greedy problem. Greedy problems are generally accompanied by sorting. Sort g[] and s[] separately. Start assigning cookies from the hardest-to-satisfy children, satisfy them one by one, and the final number of children that can be satisfied is the answer.

Code #

package leetcode

import "sort"

func findContentChildren(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	gi, si, res := 0, 0, 0
	for gi < len(g) && si < len(s) {
		if s[si] >= g[gi] {
			res++
			si++
			gi++
		} else {
			si++
		}
	}
	return res
}