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
}