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 6It 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
ways to give each child a different cookie. At the rule-of-thumb rate of 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 5The 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:
You have some children and some cookies. Child is content with any cookie of size at least g[i], the child's greed factor, and cookie 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
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.
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 comparisons each on the largest input the problem allows. If is the length of the longer list, the function takes time.
The coin problem
The cookie rule made all three children happy on our tray, and it gets both samples right. That is not yet a reason to trust it, as a second greedy rule shows.
Take a cashier who has to pay out an amount with as few coins as possible, from an unlimited supply of each kind of coin. The natural rule is to keep taking the largest coin that is not more than what is left to pay. With coins worth 1, 5, 10 and 25, the rule pays 63 as . That is six coins, and no other way of paying 63 uses fewer. With these four coin values the rule always finds the fewest coins, which takes a proof of its own (the slides under Further reading have one).
Now change the coins to 1, 4 and 6, and pay 8. The rule takes the 6, the largest coin that fits, and then has to pay the remaining 2 with two coins of 1:
The rule went wrong at its first choice, and a greedy algorithm never takes a choice back. An input like this, on which a rule gives a worse answer than the best one, is called a counterexample, and one counterexample is enough to reject a rule.
With the coins 1, 4 and 6, the rule pays every amount from 1 to 7 with the fewest coins possible, and 8 is the first amount it gets wrong. Tests on a few small amounts could easily pass, and the same rule is right for the coins 1, 5, 10 and 25. So passing tests do not show that a greedy rule is right, and the only way to be sure is to prove it. The scheduling problem below shows what such a proof looks like.
The scheduling problem
Many greedy problems are about intervals, stretches of time with a start and an end. The best known is the scheduling problem. Suppose a conference runs talks in several rooms, and you want to sit through as many complete talks as you can. Each talk has a start time and an end time, and you cannot be in two talks at once.
A talk that ends at 4 and a talk that starts at 4 do not clash, since you can walk out of one and into the other. So we write a talk from 1 to 4 as the half-open interval [1, 4), which includes its start time and leaves out its end time. Here are five talks:
time 0 1 2 3 4 5 6 7 8 9 10[0, 10) |-------------------|[1, 4) |-----|[3, 5) |---|[4, 8) |-------|[8, 9) |-|Definition
Two half-open intervals overlap when each one starts before the other ends. Otherwise one of them ends at or before the time the other starts, and you can attend both.
Three greedy rules for the schedule
Of our five talks you can attend three, [1, 4), [4, 8) and [8, 9), and no set of four works. Trying every set of talks finds this, since five talks have only sets. But each extra talk doubles the number of sets, and 40 talks already have , about three hours of work even at sets a second. So we look for a greedy rule.
A greedy algorithm for this problem goes through the talks in some order and attends each talk that does not overlap one it has already decided to attend. The order is the rule, and three orders come to mind:
- Earliest start: take the talks in order of start time, so that no time at the beginning of the day is wasted.
- Shortest first: take them in order of length, because a short talk seems to get in the way of the fewest others.
- Earliest finish: take them in order of end time, so that you are free again as soon as possible, with as many talks as possible still ahead.
Run each rule on the five talks
Choose a rule and step through its decisions on our five talks. Under the timeline, the widget compares the number of talks the rule attends with the best possible number, found by trying all 32 sets.
| Rule | Order it tries | Talks attended | What happens |
|---|---|---|---|
| Earliest start | [0,10) [1,4) [3,5) [4,8) [8,9) | 1 | [0, 10) is taken first and overlaps every other talk. |
| Shortest first | [8,9) [3,5) [1,4) [4,8) [0,10) | 2 | [3, 5) is taken second and overlaps both [1, 4) and [4, 8). |
| Earliest finish | [1,4) [3,5) [4,8) [8,9) [0,10) | 3 | It skips [3, 5) and [0, 10) and attends the other three. |
The five talks are a counterexample to earliest start and to shortest first. Earliest finish attended the best possible number, and the next section shows that it does so on every input.
Earliest finish and the exchange argument
A set of talks can have more than one best schedule, so we will not try to show that the schedule earliest finish builds is the only best one. It is enough to show that it is one of them. We start with the first talk earliest finish chooses: any best schedule can be changed to start with the talk that ends first, without losing a talk.
To see the change on an example, we need a best schedule that starts with a different talk. Our five talks have none, because the only schedule of three talks is the one earliest finish found. So let's add a sixth talk, [5, 8). Now [3, 5), [5, 8), [8, 9) is also a schedule of three talks, and trying all sets confirms that three is still the most possible.
Earliest finish would start with [1, 4), and this schedule starts with [3, 5). Exchange the two: drop [3, 5) and attend [1, 4) in its place. The other two talks start at 5 and at 8, and [1, 4) is over by 4, so it overlaps neither. The schedule still has three talks, and now it starts with the greedy choice.
[1, 4), the talk that ends first, and is the time at which [3, 5) ends.The exchange works on every input for the same reason. Let be the talk that ends first of all, and take any best schedule. Its first talk ends at some time , and its other talks all start at or after . No talk ends earlier than does, so ends at or before :
If the schedule's first talk is itself, there is nothing to change. Otherwise put in its place. Every later talk in the schedule starts at or after . Talk starts before , so it differs from all of them, and it is over by , so it overlaps none of them. The schedule is still valid and has the same number of talks. So some best schedule starts with the talk that ends first.
The same exchange works at every later step. Write the talks that earliest finish attends, in order, as , so . These talks are a schedule themselves, so a best schedule has at least talks. Take one that agrees with earliest finish up to and then has some other talk where earliest finish has . Both and start at or after the end of . Of all the talks that do, earliest finish took the one that ends first, so ends no later than .
Now put in place of , as we put in place of the first talk. Talk starts after the talks before it have ended, and it ends no later than , so it is over before the talks after it start. The schedule stays valid, keeps its size and agrees with earliest finish for one more talk.
Repeating the exchange gives a best schedule that begins with all greedy talks. It has no talk after them either. Such a talk would start at or after the end of and overlap none of the greedy talks, so earliest finish would have attended it too. So this best schedule is exactly the greedy one, and earliest finish attends as many talks as any schedule can.
Definition
A proof of this shape is called an exchange argument. Take a best solution, find the first choice where it differs from the greedy solution, and show that exchanging that choice for the greedy one keeps the solution valid and no worse. Repeating the exchange gives a best solution that contains every greedy choice, and a last check shows that it contains nothing more.
Deeper read: an exchange argument for the cookie rule
The cookie rule can be proved the same way. Call the child who needs the least the first child. The rule's first choice gives the first child the smallest cookie that is big enough. Take any best handout in which every cookie handed out is big enough for the child holding it (a cookie that is too small can be taken back without changing the count), and look at what it gives the first child.
- If the first child holds , the handout already agrees with the rule.
- If the first child holds another cookie , then is at least as big as , because is the smallest cookie this child accepts. Exchange the two cookies. The first child is happy with , and if another child was holding , that child now holds , which is at least as big.
- If the first child holds nothing, some other child must hold , since otherwise giving to the first child would make one more child happy. The other child can pass to the first child: one child becomes happy, one stops being happy, and the count stays the same.
On our tray, take the handout that gives the 4 to the child who needs 2, the 3 to the child who needs 3 and the 6 to the child who needs 5. Exchanging the 4 and the 3 leaves all three children happy and gives the first child the rule's cookie. In every case some best handout starts with the rule's choice, and the children and cookies that are left form a smaller copy of the same problem.
The earliest-finish scan in code
Here is the scheduling problem as a judge problem. It asks the question the other way round:
You get a list of intervals [start, end]. Return the fewest intervals you must remove so that no two of the remaining intervals overlap.
Intervals that only touch at a point, such as [1, 2] and [2, 3], do not overlap.
Constraints
Sample 1 · Input
intervals = [[1,2],[2,3],[3,4],[1,3]]
Output
1
Sample 2 · Input
intervals = [[1,2],[1,2],[1,2]]
Output
2
Sample 3 · Input
intervals = [[1,2],[2,3]]
Output
0
In the first sample, removing [1, 3] leaves three intervals that only touch. This problem does not count touching intervals as overlapping, so its [1, 2] behaves like our half-open [1, 2). Removing the fewest intervals is the same as keeping the most, and keeping the most is our scheduling problem. So the function counts how many intervals earliest finish keeps and subtracts that from the number of intervals.
It sorts the intervals by end time and goes through them in that order, keeping an interval when it starts at or after the end of the last interval kept:
def erase_overlap_intervals(intervals):
kept = 0
last_end = float('-inf')
for start, end in sorted(intervals, key=lambda interval: interval[1]):
if start >= last_end:
kept += 1
last_end = end
return len(intervals) - kept
print(erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]))
print(erase_overlap_intervals([[1, 2], [1, 2], [1, 2]]))
print(erase_overlap_intervals([[1, 2], [2, 3]]))Prints 1, 2 and 0, the three samples' answers.
The loop compares each interval with only one kept interval, the last one. That is enough because the intervals arrive in order of end time, so the last interval kept is also the kept interval that ends latest. An interval that starts at or after that end starts after every kept interval has ended. The comparison is >= and not >, so that two intervals that only touch are both kept.
last_end starts at float('-inf'), which is below every start time, so that the first interval in sorted order is always kept.
Sorting 100,000 intervals, the most this problem allows, takes about million comparisons, and the scan is one pass, so the function runs in time.
Worked example
Trace the earliest-finish scan
The trace runs the scan on our five talks, one interval at a time in order of end time. Its other inputs are a long talk that starts first, a talk in the middle that overlaps the other two, and two talks that touch.
1 to 4 fits after the previous choice. Choosing this earliest finish leaves at least as much room as any later finish.
- selected count
- 1
Change the example input
Current result: [[1,4],[4,8],[8,9]]
Merging overlapping intervals
The scheduling scan chose some intervals and dropped the rest. The next two problems keep every interval, and both again come down to sorting followed by one pass. The first asks which stretches of time the intervals cover together.
You get a list of intervals [start, end], both ends included. Merge every group of overlapping intervals into one interval and return the resulting non-overlapping intervals, which cover the same times as the input.
Constraints
Sample 1 · Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]
Sample 2 · Input
intervals = [[1,4],[4,5]]
Output
[[1,5]]
Sample 3 · Input
intervals = [[4,7],[1,4]]
Output
[[1,7]]
These intervals include both of their ends, so in the second sample [1, 4] and [4, 5] share the moment 4 and merge into [1, 5]. In the scheduling problem, intervals that touched did not overlap. Problems differ on this point, and it decides whether a comparison is < or <=, so look for it in the statement first.
For merging, we sort by start time. Take the first sample, which is already in that order: [1, 3], [2, 6], [8, 10], [15, 18]. We keep a current block, which begins as [1, 3]. The next interval, [2, 6], starts at 2, inside the block, so the block grows to [1, 6]. Then [8, 10] starts after the block's end of 6. Because of the sorted order, every interval still to come starts at 8 or later, so none of them can reach back into [1, 6]. That block is finished, and [8, 10] begins a new one. In the same way, [15, 18] finishes [8, 10] and becomes the last block.
def merge(intervals):
out = []
for start, end in sorted(intervals):
if out and start <= out[-1][1]:
out[-1][1] = max(out[-1][1], end)
else:
out.append([start, end])
return out
print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
print(merge([[1, 4], [4, 5]]))
print(merge([[4, 7], [1, 4]]))Prints [[1, 6], [8, 10], [15, 18]], [[1, 5]] and [[1, 7]].
In the code, the last element of out is the current block. An interval that starts at or before its end is merged into it, and the block's end becomes the larger of the two ends. The max matters when one interval lies inside another: merging [1, 10] with [2, 3] must leave the end at 10. Without it the end would move back to 3, and a later [4, 5] would wrongly start a new block. Sorting takes time, and the pass looks at each interval once.
Splitting intervals into the fewest groups
The last problem also keeps every interval. Where merging joined the intervals that overlap, this one has to keep them apart.
You get intervals [left, right], both ends included. Put every interval in exactly one group so that no two intervals in the same group share a number, and return the fewest groups you need. For example, [1, 5] and [5, 8] share 5, so they cannot share a group.
Constraints
Sample 1 · Input
intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
Output
3
Sample 2 · Input
intervals = [[1,3],[5,6],[8,10],[11,13]]
Output
1
One fact gives a lower limit on the answer. If some number lies inside of the intervals, those intervals need different groups, because any two of them share that number. In the first sample, 2 lies inside [1, 5], [1, 10] and [2, 3], so at least three groups are needed. The largest number of intervals that contain one common number is called the depth of the intervals, and the answer is at least the depth.
The depth is also enough, and a greedy rule shows it. Go through the intervals in order of start time, and put each one into any group whose last interval ended before this one starts, or into a new group if there is none. On the first sample the order is [1, 5], [1, 10], [2, 3], [5, 10], [6, 8]. The first three all contain 2, so each opens a group. Then [5, 10] cannot join group 1, because [1, 5] includes 5, and goes into group 3, whose interval ended at 3. Last, [6, 8] goes into group 1.
The rule never opens more groups than the depth. Look at the moment it opens a new group. The new interval starts at some time , and every existing group is busy. The last interval of each group started no later than , because we go in order of start time, and it has not ended, so it contains . With groups before, intervals contain , and the depth is at least . So the fewest groups you need is exactly the depth.
The problem asks only for that number, so the program computes the depth and builds no groups. An event sweep computes it: write a where an interval starts and a where it ends, sort these events by time, and add them up in order. The largest value the count reaches is the depth.
Where the goes needs care. When two events have the same time, the sort puts the first, because pairs with equal times are compared by their second item and . So with the at the end time itself, an interval that ends at 5 leaves the count before one that starts at 5 enters, which treats the intervals as half-open, like the talks. These intervals include their right end, so [left, right] must still be counted at right. The ends are whole numbers, so the goes at right + 1, the first whole number after the interval.
def min_groups(intervals):
events = []
for left, right in intervals:
events.append((left, 1))
events.append((right + 1, -1))
events.sort()
best = current = 0
for _, change in events:
current += change
best = max(best, current)
return best
print(min_groups([[5, 10], [6, 8], [1, 5], [2, 3], [1, 10]]))
print(min_groups([[1, 3], [5, 6], [8, 10], [11, 13]]))Prints 3 and 1, the two samples' answers.
The same order at equal times keeps [1, 3] and [4, 6], which share no number, from being counted together at 4. The sweep sorts events, so it runs in time.
Deeper read: building the groups with a heap
The sweep returns only the number of groups. To list the groups themselves, follow the start-order rule with a min-heap, which gives back its smallest value first. The heap holds one pair for each group: the end of its last interval and the group's number.
For each interval in order of start time, look at the smallest end in the heap, which belongs to the group that becomes free first. If it is less than the interval's left end, that group is free: pop its pair, put the interval in that group, and push the interval's right end with the same group number. Otherwise every group is busy, and the interval starts a new group, pushed with the next unused number. The size of the heap at the end is the number of groups. Each interval costs one push and at most one pop, and each of those takes time.
Common mistakes with greedy rules and intervals
Sorting by start time to keep the most intervals.
- Where it breaks
- On
[[1, 10], [2, 3], [3, 4]]the long interval comes first and blocks the two short ones. The scan keeps 1 interval where 2 can be kept, and returns2removals instead of1. - The fix
- Sort by end time.
Starting
last_endat 0.- Where it breaks
- On
[[-5, -1]]the test fails, so the only interval is skipped and the function returns1removal instead of0. - The fix
- Start
last_endbelow every possible start time.
Sorting by end time to merge intervals.
- Where it breaks
- On
[[2, 3], [5, 6], [1, 10]], already in order of end time, the pass starts blocks at[2, 3]and[5, 6]before it meets[1, 10], which overlaps both. It returns[[2, 3], [5, 10]]instead of[[1, 10]]. - The fix
- Sort by start time, so that no later interval can start inside a finished block.
Forgetting that both ends are included in the groups problem.
- Where it breaks
- Putting the at
rightinstead ofright + 1on[[1, 5], [5, 8]]ends the first interval before the second starts at 5, and returns1group instead of2. - The fix
- Put the at
right + 1.
Recall Suppose each talk had a value, and the goal were the largest total value. Does earliest finish still work?
No. Take just two talks, [1, 4) with value 4 and [3, 5) with value 7. They overlap, so you can attend only one, and earliest finish attends [1, 4) when [3, 5) is worth more. The exchange argument breaks down too, because putting one talk in place of another keeps the number of talks but not their total value. The version with values needs dynamic programming, a method from later in the roadmap.
Two more greedy problems and a later lesson
Two problems in this lesson's Problems tab are greedy but are not solved by sorting intervals. They have no worked solution above, and each note says which idea to start from.
Judge problems
- Jump Game II(opens the judge in a new tab) ↗
From position you can jump to any position up to
i + nums[i], and you want the fewest jumps to the last position. The positions that need the same number of jumps form a block of neighbours, and the next block ends at the farthest position the current block can reach. One pass that tracks this farthest reach counts a jump each time it arrives at the end of a block, and stops before the last position, where no jump is made. - Candy(opens the judge in a new tab) ↗
Each child in a line gets at least one candy and more than any neighbour with a lower rating, and you want the smallest total. Handle one side at a time: a pass from left to right gives each child one candy, or one more than the left neighbour when the child's rating is higher, and a pass from right to left does the same against the right neighbour and keeps the larger count. The answer is the sum of the counts.
Related chapters
- DP fundamentals →
This lesson solves the coin problem for any coin values, including 1, 4 and 6, by working out the fewest coins for every amount up to the target.
Further reading
- USACO Guide, SilverGreedy Algorithms with Sorting(opens in a new tab)
The module this lesson follows: a first sort-and-take example, the scheduling problem with earliest start shown to fail and earliest end shown to work, then coin change and knapsack as cases where greedy fails, and a graded problem list.
- CSES Problem SetMovie Festival(opens in a new tab)
The scheduling problem as a judge task with up to 200,000 movies: read the start and end times and print the most movies you can watch in full.
- Antti Laaksonen (PDF)Competitive Programmer’s Handbook, Chapter 6: Greedy algorithms(opens in a new tab)
Pages 57 to 61: a coin system where the largest-coin rule works and one where it fails, three scheduling rules tried on counterexamples until the earliest-ending rule survives, then tasks with deadlines, where exchanging two neighbouring tasks proves the best order.
- Kevin Wayne, slides for Kleinberg and Tardos (PDF)Greedy Algorithms I(opens in a new tab)
Coin changing with a proof for U.S. coins, then interval scheduling and interval partitioning, the same two problems as the earliest-finish and fewest-groups parts, each with its proof, then scheduling to minimize lateness.
- Jeff Erickson (PDF)Algorithms, Chapter 4: Greedy Algorithms(opens in a new tab)
Ordering files on a tape by an exchange of neighbours, the class-scheduling problem with its proof that earliest finish is optimal, and the general pattern of an exchange argument, then Huffman codes. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- OI Wiki, in Chinese贪心 (Greedy)(opens in a new tab)
Proving greedy rules by exchange, the adjacent-swap method for choosing a sort order, and greedy with regret, which undoes an earlier choice when a better one arrives.
- WikipediaInterval scheduling(opens in a new tab)
The earliest-finish rule and its proof, and the weighted version, where each interval has a value, solved with dynamic programming.