The greedy idea and activity selection

Why it matters

Many problems ask you to pick the best set of things from a long list: meetings, jobs, coins, parcels, or network links. A brute force search tries every possible set. That is correct, but the number of sets doubles each time you add one item, so a list of 40 items already has more than a trillion sets. A greedy algorithm avoids that explosion. It makes one good-looking choice after another, and for many problems the final result is still the best possible answer.

Greedy code is often short. A complete solution to the problem in this lesson fits in about twenty lines. The hard part is not typing the code. The hard part is choosing the right rule and being able to justify it. Interviewers ask "why does this work?" far more often than they ask you to type a loop, so this lesson spends as much time on the reasoning as on the code.

Words you will need

• Algorithm: a fixed sequence of steps that turns an input into an output.
• Greedy algorithm: an algorithm that builds an answer one step at a time. At each step it takes the choice that looks best at that moment, and it never goes back to change an earlier choice.
• Brute force: trying every possible answer and keeping the best one. It is slow but easy to trust.
• Interval: a span of time with a start and an end. This module writes an interval as [start, finish). The square bracket on the left means the start moment is included. The round bracket on the right means the finish moment is not included.
• Clash (also called overlap): two intervals clash when they share at least one moment in time. A half-open interval ends just before its finish, so [1, 3) and [3, 5) do not clash.
• Sort: rearranging a list into an order, such as smallest to largest.
• Comparator: a rule that tells a sort function whether one item should come before another.
• Lambda: a small function written in place, with no name. You give it to another function, such as sort.
• Vector: a C++ container that holds a list of items in one block of memory. It can grow when you add items.
• Big O notation: a short way to describe how the number of steps grows when the input grows. O(n) means the steps grow in proportion to n. O(n log n) grows a little faster than n, and is the usual cost of a good sort.

The suitcase idea

Imagine packing a small suitcase for a trip. You have room for only a few things. A greedy packer picks up the most useful item first, then the next most useful item that still fits, and so on. The packer never takes an item out again to make room for a better one. Packing like this is quick. You make one pass down a sorted list of items, and you are done.

The packing story also shows that this method is not always the best. Suppose the most useful item is so big that it blocks three smaller items, each of which is almost as useful. The greedy packer takes the big item and loses. The method only works when the rule for "most useful" is the right rule for the problem.

Every greedy solution has two parts. The first part is a rule that sorts the choices into the order you want to try them. The second part is a single pass down that sorted list, taking each choice if it still fits. Changing the rule can change the answer completely, so the rule is the real work. Most of the time spent on a greedy problem goes into choosing and testing the rule.

Two properties decide whether greedy is correct. You can check them for any new problem.

• Greedy choice property: some best overall answer contains the choice that greedy makes first.
• Optimal substructure: once the first choice is made, the rest of the problem is a smaller copy of the same problem. The best answer to the smaller problem, combined with the first choice, gives the best answer to the whole problem.

If both properties hold, you make the greedy choice, shrink the problem, and repeat. Lesson 4 turns these properties into a proof that you can write on paper. For now, keep them in mind as the two questions to ask about any rule you invent.

Sorting with a comparator

Greedy algorithms almost always start by sorting. A sort puts the items into the order the rule wants. In C++ the standard way is std::sort, which lives in the <algorithm> header. The line using namespace std; lets you write sort instead of std::sort.

A call to sort needs three things: the position of the first item, the position just after the last item, and a comparator. Here is the shape of the call:

sort(list.begin(), list.end(), comparator);

list.begin() gives the position of the first item. list.end() gives the position just after the last item. This range is half-open, the same way the time intervals are. The first position is included and the end position is not, so the whole list is covered exactly once.

The comparator is the rule. It is a function that takes two items and returns true when the first item should come before the second. Here is a comparator that puts a meeting with an earlier finish time first:

[](const Meeting& a, const Meeting& b) { return a.finish < b.finish; }

Read it in parts. The square brackets at the start are the capture list. Nothing is captured here, so the brackets are empty. The round brackets hold the parameters. const Meeting& means the function looks at each meeting through a reference, which avoids copying it, and promises not to change it. The body returns the comparison. You do not need to write return on a separate line, and you do not need a name for the function, because sort is the only place it is used.

A comparator must describe a strict order. An item is never before itself, and if a is before b, then b must not also be before a. If you break these rules, sort can misbehave. A common slip is writing <= where you meant <. Use < for a sort comparator.

The default sort with no comparator sorts plain numbers from smallest to largest. You need a comparator as soon as you sort structs, or when you want a different order such as largest first.

The activity selection problem

You have one meeting room and a list of meetings. Each meeting is an interval with a start and a finish. Two meetings clash when they overlap. A meeting that starts at the exact moment another one finishes does not clash with it, because the room is free again at that moment.

Your task is to choose the largest number of meetings that do not clash with each other. This is called activity selection. It is one of the cleanest greedy problems, and it is a standard interview question.

Before you write any code, list the rules that sound plausible:

• Earliest start first.
• Shortest meeting first.
• Earliest finish first.

Each rule sounds reasonable, and each one needs a test. You can test a rule by inventing a small list of meetings where it fails. If you find a failing list, the rule is wrong, no matter how often it works on other lists. The next two sections show the failing lists for the first two rules, and the last section explains why the third rule always works.

Two rules that fail

Earliest start first fails because a meeting that starts early may also finish very late. Take [0, 10), [1, 2), [3, 4) and [5, 6). The earliest start is [0, 10). Choosing it blocks the room until time 10, so you keep only one meeting. The best choice is the three short meetings, which give three.

Shortest meeting first fails because a short meeting can sit in the middle of two longer meetings and clash with both. Take [1, 5), [4, 6) and [5, 9). The shortest meeting is [4, 6), which is 2 long. It clashes with [1, 5), because they share the moments from 4 to 5. It also clashes with [5, 9), because they share the moments from 5 to 6. Choosing it leaves you with one meeting. The other two meetings, [1, 5) and [5, 9), do not clash with each other, so they give two.

Why earliest finish is the right rule

Think about what each meeting costs you. A meeting uses up the room from its start until its finish. The finish time tells you when the room becomes free again for the next choice. A meeting that finishes early leaves the largest possible window of time after it. The earliest-finish rule keeps as much room as possible for the meetings that come later, and that is the whole idea.

Compare that with the earliest-start rule. An early start says nothing about how long the room stays busy. A meeting that starts first might run until the end of the day, and blocking the room is exactly what you want to avoid. The finish time is the number that matters for the rest of the schedule.

The shortest-meeting rule measures the wrong thing. Length tells you how long a meeting lasts, but not where it sits. A short meeting in the wrong place can still clash with two meetings on either side. The finish time takes position into account, because it is a position on the timeline.

So sort by finish time, then walk down the list. Keep a value called lastFinish, which is the finish time of the last meeting you chose. A meeting is free to choose when its start is at or after lastFinish. If it is, choose it and update lastFinish. If not, skip it.

A worked example by hand

Take six meetings: [1, 2), [3, 4), [0, 6), [5, 7), [8, 9) and [5, 9). Work through them by hand before you look at any code.

Step 1 is the sort by finish time. The finish times are 2, 4, 6, 7, 9 and 9. The sorted order is [1, 2), [3, 4), [0, 6), [5, 7), [8, 9) and [5, 9). Two meetings finish at time 9. Their order between each other does not change the answer, as the Variations section explains.

Step 2 sets lastFinish to a value before any meeting can start. Use -1, because every start time here is 0 or more. The count starts at 0.

Step 3 is the one-pass walk. Here is the table of what happens to each meeting.

The answer is 4. The chosen meetings are [1, 2), [3, 4), [5, 7) and [8, 9).

Six meetings on a timeline, with the four meetings the greedy walk picks highlighted

Notice what the greedy method did not do. It never went back to swap [5, 7) for something else, and it never tried to fit a second meeting into a gap it had already passed. Each decision was final, and the final answer is still the best one. Lesson 4 explains why that is true.

Notice also what the long meeting [0, 6) did. It was skipped, because its start of 0 was before the last finish of 4. Greedy did not care that [0, 6) was long. It only cared that the meeting clashed with a meeting already chosen, and that the chosen one finished earlier.

Program 1: the greedy in C++

The program below reads the meetings from the keyboard and prints the ones it chooses. Click Run. In the Input box, type the following six lines, then press Run.

6
1 2
3 4
0 6
5 7
8 9
5 9

The first number is the count of meetings. Each of the next lines holds one meeting: its start, then its finish.

The output you should see:

pick [1, 2)
pick [3, 4)
pick [5, 7)
pick [8, 9)
total 4

Here is what each part does. struct Meeting groups two numbers under one name, so you can pass a meeting around as one value. cin >> n reads the first number from the Input box. vector<Meeting> meetings(n) creates a list of n meetings whose numbers are zero, ready to be filled. The loop for (Meeting& m : meetings) visits each meeting in turn, and the & means m is the real meeting in the list, not a copy, so writing to m fills in the list. cin >> m.start >> m.finish reads two numbers. The reading skips spaces and line breaks, so the layout of the input does not matter as long as the numbers arrive in the right order.

The sort comes next, and the comparator is the greedy rule written in code. The walk after the sort is the one-pass part. The test m.start >= lastFinish is the whole decision. Everything else is bookkeeping for printing.

The starting value -1 for lastFinish needs a word of explanation. It must be smaller than every start time, so that the first meeting always fits. In this program every start time is 0 or more, so -1 works. If your start times can be negative, use INT_MIN from the <climits> header instead, which is the smallest possible int.

What happens inside the computer

When vector<Meeting> meetings(n) runs, the computer reserves one block of memory big enough for n meetings. Each Meeting holds two int values. An int usually takes 4 bytes, so a meeting takes 8 bytes. Six meetings take 48 bytes in one block, and the meetings sit side by side. The loop that reads the input writes into that block one meeting at a time.

sort works inside that same block. It does not make a second copy of the list. It swaps positions of the meetings until they are in the right order. The C++ standard library usually builds sort from three methods: quicksort, heapsort and insertion sort. It starts with quicksort, changes to heapsort if the recursion gets too deep, and uses insertion sort for small pieces. You do not need the details of each method to use sort. You only need to know that it makes about n log n comparisons, and that every comparison calls your lambda.

The visualizer below sorts a list of numbers. It is not about meetings, but the moves are the same. A sort by finish time only compares the finish fields, and moves whole meetings around in the same way the numbers move in the picture.

Watch how the pivot splits the list into a smaller group and a larger group, and how each group is sorted in turn. When you run Program 1, the sort does the same kind of work, except that each comparison looks at a finish time.

The one-pass walk does something simpler. It reads each meeting once, in order, and it keeps only two numbers: lastFinish and count. Its memory use does not grow with the number of meetings, which is why the extra space is small.

Why the sort is needed

Without the sort, the one-pass walk makes choices in whatever order the input happened to arrive. Consider the list [0, 10), [1, 2), [3, 4) and [5, 6) in that order, with no sort. The walk takes [0, 10) first, because its start is 0 and lastFinish begins at -1. Then it skips the three short meetings, because they all start before 10. The answer is 1.

Sort the same list by finish time and the walk takes [1, 2), then [3, 4), then [5, 6). It skips [0, 10) at the end. The answer is 3. The sort is what turns the walk into a rule that gives the best answer.

Program 2: comparing three rules

The program below runs the same one-pass walk three times. Each run sorts a copy of the list with a different rule. It prints how many meetings each rule chooses. Type the four-meeting input below into the Input box, then press Run.

4
1 5
4 6
5 9
0 10

The output you should see:

earliest finish: 2
earliest start: 1
shortest first: 1

Check the earliest-finish line by hand. The sorted order is [1, 5), [4, 6), [5, 9), [0, 10). The walk takes [1, 5), skips [4, 6) because 4 is before 5, takes [5, 9) because 5 is at or after 5, and skips [0, 10). The answer is 2.

The earliest-start line picks [0, 10) first, because 0 is the smallest start, and then skips everything else. The answer is 1. The shortest-first line picks [4, 6) first, which is 2 long, and then skips the other two. The answer is also 1.

The template is worth a look. template <typename Rule> lets greedyCount accept any comparator. The three lambdas are different types, so the template makes three versions of the function, one for each rule. You pass the rule in as an ordinary argument, which keeps the three runs in one place and makes the comparison easy to read.

Program 3: checking a plan

Interviewers and reviewers often ask you to check an answer, not only to produce one. A checker takes a proposed plan and confirms it has no clashes. It is also a good habit to write one for your own work, because it catches mistakes in the greedy rule.

Type the three-meeting plan below into the Input box and press Run. Then run it again with the second plan, which is shown after it.

3
1 4
3 6
7 9

With the first plan, the output is:

clash between [1, 4) and [3, 6)

The second plan is 3, then 1 2, 3 4 and 5 7. Its output is:

valid, 3 meetings

The checker has one subtle point. It compares each meeting only with the one before it. That works here because the plan is in order by start. A plan that is not in order would need a sort first. Notice also the first check, which catches a meeting whose start is not before its finish. A checker is only as good as the cases it covers, so write checks for the edge cases you can imagine, not only for the normal case.

Program 4: tracing the walk

A trace shows each decision as it happens. Tracing is the most reliable way to debug a greedy program, because it turns a wrong final answer into a list of small decisions you can check one by one. The program below is the same as Program 1, with a line printed for each meeting. Use the same six-meeting input as Program 1.

6
1 2
3 4
0 6
5 7
8 9
5 9

The output you should see:

look at [1, 2): last finish is -1, start is not before it, so pick
look at [3, 4): last finish is 2, start is not before it, so pick
look at [0, 6): last finish is 4, start is before it, so skip
look at [5, 7): last finish is 4, start is not before it, so pick
look at [8, 9): last finish is 7, start is not before it, so pick
look at [5, 9): last finish is 9, start is before it, so skip
total 4

Compare this trace with the table in the worked example. The two match line for line, which is what a good trace should do. When your own program gives a wrong answer, add a line like this to it, run the same input, and check each decision against what you expected by hand. The first line that disagrees with your hand trace is where the bug is.

Complexity

The sort takes O(n log n) time. The walk that follows reads each meeting once, which takes O(n) time. The total is O(n log n), because the sort grows faster than the walk. This is the cost you should quote in an interview.

Extra space is small. The walk keeps two numbers. The sort uses a small amount of stack space for its recursion, about O(log n). The meetings themselves are the input, and the sort rearranges them in place, so there is no second list.

Note that the sort is what sets the total cost. If the input were already sorted by finish time, the walk alone would take O(n), but you cannot count on that. Always assume you must sort.

Thinking out loud in an interview

An interviewer cannot see what you are thinking unless you say it. For a greedy problem, a good order of talk looks like this. First, restate the problem in one sentence, with the input and the output. Second, name the rule you want to try, and say why it sounds right. Third, try to break the rule with a small example of three or four meetings. If you find a counterexample, say so and try another rule. If you cannot find one, say that you will prove it, and sketch the exchange argument from lesson 4. Last, write the code, and state the complexity.

Saying the failed rule out loud is useful, not embarrassing. Interviewers want to see that you test ideas before you trust them. A candidate who says "earliest start might pick one long meeting, so that is wrong, earliest finish leaves the most room" is showing exactly the thinking they hope for.

Keep your examples small and concrete. Three meetings are enough to break most wrong rules, and a three-meeting example is easy to check on a whiteboard. Large random examples prove nothing about correctness, because a wrong rule can look right on most random inputs and still fail on a rare one.

When you write the code, keep the greedy rule on its own line, usually the sort comparator, so the interviewer can point at it and ask about it. Name the variables after the ideas, such as lastFinish, not x and y. A reader should be able to follow the rule from the code without reading the rest of the program.

Common mistakes

Forgetting the sort. Without it, the walk takes meetings in whatever order they were given. The example above with [0, 10) first shows the damage: the answer drops from 3 to 1. If your answer changes when you shuffle the input, you probably forgot to sort.

Sorting by the wrong key. Sorting by start time or by length is the most common wrong idea. Both have counterexamples, as shown earlier in this lesson. Check the comparator line by line. The field name in the comparator should be finish for this problem.

Using > instead of >= in the clash test. The test must allow a meeting to start at exactly the moment the last one ends. With >, the meetings [1, 3) and [3, 5) are treated as clashing, and you lose one meeting. Test your program on that case.

A comparator that is not a strict order. Writing a.finish <= b.finish looks like a small change. It can make sort read past the end of the list, which is undefined behaviour in C++. The program may crash, or it may print a wrong answer that changes from run to run. Always use < in a sort comparator.

Missing the algorithm header. If you leave out #include <algorithm>, the compiler stops with an error. With g++ 15 the message is:

error: ‘sort’ was not declared in this scope; did you mean ‘short’?

The message says the name sort is unknown. The fix is to add #include <algorithm> at the top. The "did you mean" hint suggests a similar name, which is a clue that the name is not known in this scope and not that the name is spelled wrong.

Debugging walkthrough

Suppose your program prints 3 for the six-meeting input, but the correct answer is 4. Do not guess. Follow these steps.

First, print the sorted list. Add a loop after the sort that prints each finish time. You should see 2, 4, 6, 7, 9, 9. If the order is different, the comparator is wrong.

Second, trace the walk, as in Program 4. Compare each decision with the table in the worked example. A common bug shows up at [8, 9): if the program compares with lastFinish before updating it, it skips a meeting it should take.

Third, try the edge cases. A meeting that touches the end of the last one, such as [3, 4) after [1, 3), is a frequent source of off-by-one errors. Test that case on its own.

Once you have found the bad line, fix only that line and run the same input again. Keeping the other lines the same helps you know that your fix caused the change.

Variations and edge cases

No meetings. If n is 0, the vector is empty, the loop never runs, and the answer is 0. No special case is needed.

Meetings that touch. The meetings [1, 3) and [3, 5) do not clash, so both can be chosen. The test >= handles this.

Two meetings with the same finish time. Suppose [5, 9) and [8, 9) are both in the list. The sort may put either one first. Choosing either one sets lastFinish to 9. Any later meeting must start at 9 or later to fit after either choice, so the two choices lead to the same future. The count is the same, although the chosen meeting may differ.

One meeting. The answer is 1. The walk takes it, because its start is at or after -1.

Zero-length meetings. A meeting with start equal to finish, such as [5, 5), takes no time. The problem in this lesson assumes start is less than finish. If your task allows zero-length meetings, decide how they count before you write the code, and say so in your answer.

Negative times. Use INT_MIN as the starting value of lastFinish, as described earlier.

Very large numbers. If finish times can reach about two billion, a sum of two finish times can overflow an int. This lesson only adds numbers to a start time, so overflow is not a risk here. Use long long if you ever add two times together.

Interview questions you will hear

The interviewer usually asks three things. Why does earliest finish work? You answer with the exchange argument from lesson 4. What is the complexity? You say O(n log n) and explain that the sort dominates. What if each meeting has a value, and you want the largest total value? Greedy fails for that version. It is called weighted interval scheduling, and it is solved with dynamic programming in module 26. Saying that the greedy rule does not transfer, and why, is a strong answer.

A related question asks for the fewest rooms needed to hold every meeting. That is a different problem. The answer is the largest number of meetings that overlap at any one moment. Lesson 3 uses a min-heap to solve a version of it, and the coding problems for this module include it.

Practice

1. Easy. Trace by hand. Use the earliest-finish rule on [0, 3), [2, 4) and [4, 6). Which meetings are chosen, and what is the count?

2. Easy. Write a comparator. Write the lambda that sorts meetings so that the latest start comes first.

[](const Meeting& a, const Meeting& b) { return a.start > b.start; }

3. Easy. Spot the bug. A student writes the clash test as if (m.start > lastFinish). Give a two-meeting input where this gives a smaller answer than the correct one.

4. Medium. Negative start times. The program starts lastFinish at -1. Give a one-meeting input where the answer is 0 with -1 but 1 with INT_MIN.

5. Medium. Show that start-time greedy fails. Find a three-meeting list where the earliest-start rule gives a smaller answer than the earliest-finish rule.

6. Medium. Keep the original order in the output. Change Program 1 so it prints the chosen meetings in the order they appeared in the input.

struct Meeting {
    int start;
    int finish;
    int index;  // position in the input
};

7. Medium. Read start and length. Some input lists give a start time and a length instead of a finish. Change Program 1 to read start length pairs and compute the finish.

8. Medium. Touching is a clash. Change the rule so that a meeting clashing with the previous one at exactly its end moment also counts as a clash. Which single character changes?

9. Hard. Exchange argument in three sentences. Explain in three sentences why the earliest-finish meeting can always be part of some best answer.

10. Hard. Count the rooms. Given the same kind of list, find the fewest rooms needed to hold every meeting, so that no two meetings in the same room clash. Describe the method in plain words.

What you now know

• A greedy algorithm takes the best-looking choice at each step and never goes back.
• A greedy solution has a sorting rule and a single pass. The rule is the hard part.
• Two properties decide correctness: the greedy choice property and optimal substructure.
• A C++ comparator is a lambda that returns true when the first item should come first, and it must use a strict <.
• For activity selection, sort by finish time, keep lastFinish, and take a meeting when its start is at or after lastFinish.
• Earliest start and shortest first both fail, and you can prove it with a small counterexample.
• The solution runs in O(n log n) time, dominated by the sort, and uses small extra space.
• A trace that prints each decision is the fastest way to find a bug in a greedy program.