Arrays and searching 0/120

Lesson 7 of 9

Greedy and intervals

Prove a greedy rule with an exchange argument, pick the most non-overlapping intervals by earliest finish, and merge and group sorted intervals.

4,786 words · 22 min read

Part 1 of 10 A first greedy rule

A first example: handing out cookies

Suppose you have a tray of cookies to hand out to a group of children. Each child wants a cookie of at least a certain size and gets at most one cookie, and you want to make as many children happy as you can. Here are three children and four cookies:

children need   2  3  5cookie sizes    1  3  4  6

It matters which cookie goes to which child. If you give the cookie of size 6 to the child who needs 2 and the 3 to the child who needs 3, the child who needs 5 is left with the 1 and the 4, and neither is big enough. That handout makes two children happy. Giving the 3, the 4 and the 6 to the children who need 2, 3 and 5 makes all three happy.

You could find the best handout by trying every one, but the number of handouts grows very fast. With 20 children and 20 cookies there are

20!=2,432,902,008,176,640,000≈2.4×101820! = 2{,}432{,}902{,}008{,}176{,}640{,}000 \approx 2.4 \times 10^{18}

ways to give each child a different cookie. At the rule-of-thumb rate of 10810^8 simple operations a second, that is more than 700 years of checking.

This lesson is about a much faster way to build an answer: make one choice at a time by a simple rule, and never go back to change a choice already made. For the cookies, the rule is to take the child who needs the least and give that child the smallest cookie that is big enough. Here is what the rule does on our tray, cookie by cookie from the smallest:

cookie 1   too small for everyonecookie 3   to the child who needs 2cookie 4   to the child who needs 3cookie 6   to the child who needs 5

The 1 is too small even for the child who needs 2, so it goes to no one. Each of the other cookies, taken in turn, is the smallest one left and is big enough for the child who now needs the least, so it goes to that child. All three children are happy, and no choice had to be undone.

The rule starts with the child who needs the least because that child is the easiest to make happy, and a cookie that is too small for that child is of no use to anyone. It asks for the smallest cookie that is big enough because a bigger one gains nothing and may be the only cookie that a child who needs more can use. That is what went wrong in the first handout above, where the 6 went to the child who needs 2.

An algorithm that works this way is called a greedy algorithm. It makes the choice that looks best right now by some simple rule, then deals with what is left in the same way, and it never goes back to try a different choice. Since it tries no alternatives, a greedy algorithm is usually short and fast. The hard part is choosing the rule, because a rule that sounds sensible can give wrong answers on some inputs, as the coin problem below shows.

The cookie rule in code

Here is the same task as a judge problem:

Difficulty tier:Very Easy

You have some children and some cookies. Child ii is content with any cookie of size at least g[i], the child's greed factor, and cookie jj has size s[j]. Each child gets at most one cookie and each cookie goes to at most one child.

Return the largest number of children you can make content.

Constraints

  • 1≤g.length≤3×1041 \le g.\text{length} \le 3 \times 10^4
  • 0≤s.length≤3×1040 \le s.\text{length} \le 3 \times 10^4
  • 1≤g[i],s[j]≤231−11 \le g[i], s[j] \le 2^{31} - 1

Sample 1 · Input

g = [1,2,3], s = [1,1]

Output

1

Sample 2 · Input

g = [1,2], s = [1,2,3]

Output

2

To follow the rule, the function sorts both lists and goes through the cookies from smallest to largest. The variable child is the position, in sorted order, of the child who needs the least among those still waiting.

Sign up to run
def find_content_children(g, s):
    g, s = sorted(g), sorted(s)
    child = 0
    for cookie in s:
        if child < len(g) and cookie >= g[child]:
            child += 1
    return child


print(find_content_children([1, 2, 3], [1, 1]))
print(find_content_children([1, 2], [1, 2, 3]))
print(find_content_children([2, 3, 5], [1, 3, 4, 6]))

Prints 1 and 2, the two samples' answers, then 3 for our tray.

The loop follows the table above. A cookie that is big enough goes to the waiting child, and child moves on to the next one. A cookie that is too small for the waiting child is too small for everyone after that child, and the loop passes over it. The first half of the test keeps the code from reading past the end of g once every child has a cookie. When the loop ends, child is the number of children who got a cookie.

The two sorts are most of the work: about 30,000×log⁡230,000≈446,00030{,}000 \times \log_2 30{,}000 \approx 446{,}000 comparisons each on the largest input the problem allows. If nn is the length of the longer list, the function takes O(nlog⁡n)O(n \log n) time.