The greedy idea and activity selection in Python

Why this lesson matters

Many real problems ask you to choose the best set of things from a pile. Room bookings, delivery slots, a budget for shopping, and file compression all have this shape. A greedy algorithm is the simplest way to solve such a problem: you make one choice at a time, commit to it, and move on. Greedy ideas also produce many interview questions, because a rule that looks correct can be wrong, and the interviewer wants to see whether you can tell the difference.

By the end of this lesson you will be able to state the greedy idea in one sentence, solve activity selection in Python with a sort and one loop, explain why the sort key matters, and test a rule on a small case before you trust it.

Start from first principles: what is a choice?

A program solves a problem by making decisions. A decision is a choice between options. Which room should I book? Which coin should I hand back? Which item goes into the bag? Some programs try every combination of options and keep the best result. That approach is called brute force. It is always correct if you check every case, but it grows very fast. With 20 meetings there are about one million ways to pick a subset of them. With 40 meetings there are about a trillion.

A greedy algorithm takes a different route. It makes one choice, commits to it, and moves on. The word greedy describes its habit: it grabs what looks best at this moment. It never comes back to change an earlier decision. That makes it fast, usually a sort followed by one pass through the data.

Greedy can work for one simple reason. Each choice leaves a smaller problem behind. If the choice you make now leaves the best possible smaller problem, then making good choices in order gives the best overall answer. The hard part is not writing the loop. The hard part is knowing that the choice you make is safe. Most of this module is about recognising safe choices and proving them.

An everyday analogy

Imagine you are a tourist with one day in a city. Each attraction is open for a fixed window of time. You can visit only one attraction at a time, and you cannot leave a museum half way through a tour to walk to another. You want to see as many attractions as possible. Which one do you visit first?

A sensible tourist looks at the schedule and asks: which attraction closes soonest? Visiting that one first leaves the most time for the rest of the day. That is the greedy idea in action. Pick the option that finishes earliest, so that as much time as possible stays free.

Another tourist might pick the attraction that opens first, or the one that takes the least time. Both sound reasonable. As you will see in this lesson, one of these rules is correct and the others are not. The analogy is only a way to start thinking. The precise version comes next.

Cashiers use the same habit. To give change for 41 cents, a cashier hands over one quarter, then one dime, then one nickel, then one penny, always taking the largest coin that fits. For ordinary coin sets, that works. Lesson 4 shows a coin set where it fails.

The greedy recipe, in two parts

Every greedy solution has two parts. Keep them separate in your head.

1. The rule. This says which option to pick next. For example: "the meeting that ends earliest among those still allowed."
2. The reason. This is a short argument that the rule is safe. It shows that picking by the rule never makes the final answer worse. Lesson 4 covers this part in detail.

Many students learn only the rule. They test it on the example in the textbook, see the right answer, and move on. That is a mistake. A rule is not a solution until you can explain why it is safe, and interviewers test exactly that. In an interview, "it looks right" is not an answer.

Activity selection, defined

Activity selection is the classic greedy problem. Here is the setup in plain words.

• You have one meeting room.
• There are many meeting requests. Each request has a start time and an end time. A meeting from 2 to 5 uses the room during the time between 2 and 5.
• Two meetings overlap if both use the room at the same moment. Two meetings do not overlap when one ends before the other starts, or when one ends at the exact moment the other starts. A meeting that ends at 5 and a meeting that starts at 5 can both be held. This detail matters a lot, so remember it.
• Your job is to pick the largest number of meetings that do not overlap.

Notice what the problem does not ask. It does not ask for the total length of the meetings, or for their value. It asks for a count. A two-minute meeting counts as much as a two-hour meeting. That detail changes which greedy rule is correct.

Each meeting is a pair of numbers, (start, end). In Python, a pair like this is a tuple. A tuple is a fixed group of values written in round brackets, and its values cannot be changed after it is made. The list meetings = [(0, 4), (3, 6), (5, 10)] holds three meetings. Index 0 of a meeting is its start, and index 1 is its end. If you have not used lists before, think of a table with one row per meeting and two columns. Module 8, on arrays, covers lists in full.

Testing three rules on a small set

Before you write any code, test rules on a small example. Take three meetings: (0, 4), (3, 6) and (5, 10). Here is what happens with three natural rules.

Rule A: earliest start first. Sort by start. The order is (0, 4), (3, 6), (5, 10). Take (0, 4). Next is (3, 6), which starts at 3, before 4, so it overlaps and is skipped. Then (5, 10) starts at 5, which is at least 4, so it is taken. Result: 2 meetings.

Rule B: shortest first. The lengths are 4, 3 and 5. The shortest meeting is (3, 6), with length 3. Take it. Now both other meetings start before 6, so both overlap it. Result: 1 meeting. That is wrong, because 2 meetings are possible.

Rule C: earliest end first. Sort by end. The order is (0, 4) ending at 4, (3, 6) ending at 6, (5, 10) ending at 10. Take (0, 4). Skip (3, 6). Take (5, 10). Result: 2 meetings. Correct.

Rule A also gave the right answer here. It fails on other inputs. Take one very long meeting (0, 100) plus two short ones, (1, 2) and (3, 4). Earliest start picks (0, 100) first, and nothing else fits, so the count is 1. Earliest end takes (1, 2) and (3, 4), a count of 2. So rule A is not safe.

Rule B fails on the three-meeting example. Rule C survived both tests. That is not yet a proof. It is evidence that tells you where to look. In lesson 4 we prove it.

In Python, each rule is one key function. Worked example 2 runs all three.

The habit to build is this. Whenever a greedy rule comes to mind, try at least three small examples. Include one example where the obvious choice looks like a trap. If the rule survives all of them, you have a candidate that is worth proving.

Why earliest end works, in words

Here is the intuition, before the formal proof. Suppose someone gives you the first meeting to hold, and that meeting ends at time t. The rest of your schedule must start at or after t. A meeting that ends earlier leaves a longer stretch of time for the rest, so it can never block more later meetings than a meeting that ends later.

Now apply that to the first choice. Among all meetings, the one that ends earliest blocks the least future time. If an optimal schedule starts with some other meeting that ends later, you can swap in the earliest-ending meeting and the schedule stays valid. The count does not drop, because the swap only frees time. That swap argument is the heart of the proof, and lesson 4 writes it out step by step.

Back to the tourist. If you visit the attraction that closes soonest first, you have not made any later visit impossible that another order would have allowed. Visiting a later-closing attraction first can only use up more of the day.

What happens in memory

Before the algorithm runs, the meetings sit in memory. The list meetings holds references to the tuples. A reference is a pointer: it records where an object lives in memory, and the list does not hold the tuple itself. Here is a picture of the three-meeting example. Each line is one meeting.

meetings
  [0] -> (0, 4)     <- meeting (0,4): start 0, end 4
  [1] -> (3, 6)     <- meeting (3,6): start 3, end 6
  [2] -> (5, 10)    <- meeting (5,10): start 5, end 10

Python has two ways to sort a list. sorted(meetings, key=...) returns a new list that holds the same references in a new order. The original list stays as it was. meetings.sort(key=...) changes the list in place and returns None. The tuples themselves never move or change in either case, so each row keeps its two numbers.

This difference causes a common mistake, which the mistakes section shows. The picture is also useful when you trace a program by hand. Write the tuples on paper, sort them by hand using the key, and then walk down the sorted rows with last_end. That is the exact order the computer uses.

The algorithm, step by step

1. Sort all meetings by end time, earliest first.
2. Set last_end to a value that no start time can be before. Python has no smallest int, so use float("-inf"). It is smaller than every number, so the first meeting always fits.
3. Walk through the sorted list in order. For each meeting, if its start is at least last_end, take it and set last_end to its end. Otherwise skip it.
4. The number of taken meetings is the answer.

In an interview you might say it like this: "Sort by end time. Keep the end of the last meeting I accepted. Accept a meeting if it starts at or after that end. Count the accepted meetings."

The check is start >= last_end, not start > last_end. A meeting that starts at the exact moment the last one ends does not overlap it. Using the strict version wrongly rejects back-to-back meetings. The worked example 3 section shows what that does to the count.

Worked example 1: the eleven-meeting set

Here is a larger set that appears in many textbooks. There are eleven meetings:

(1,4) (3,5) (0,6) (5,7) (3,9) (5,9) (6,10) (8,11) (8,12) (2,14) (12,16)

Step 1 is sorting by end time. When two meetings end at the same time, either can come first, and the count is the same. After sorting, the order is (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16).

Now walk through it. The table shows the decision for each meeting and the value of last_end after the decision.

The answer is 4 meetings: (1,4), (5,7), (8,11) and (12,16). Look at what each row needs. It needs only one number, last_end. The algorithm never looks back at an earlier row and never revisits a decision. That is why the loop is so short.

Here is the Python program for this set. The meetings are written into the program, so there is no input to type. Press Run.

Output:

sorted by end: [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
4
(1,4) (5,7) (8,11) (12,16)

Read the program from top to bottom. The first block is the list of meetings. The sorted call with key=lambda m: m[1] is the greedy rule. A lambda is a short function written on one line. lambda m: m[1] means: for a meeting m, the key is its end, which is index 1. The loop is the greedy step. for start, end in ordered unpacks each tuple into two names, so start gets index 0 and end gets index 1. The list chosen only records which meetings were taken, so that you can see the answer. It is not part of the algorithm.

The line print(" ".join(f"({s},{e})" for s, e in chosen)) uses an f-string. A string that starts with f can hold expressions inside braces, and Python replaces each one with its value. Here the braces hold s and e.

Python integers have no fixed size, so the times can be as large as you need. Lesson 2 shows a case where you need decimals.

Keys and comparators

What happens inside the sort

Python's sorted and list.sort use an algorithm called Timsort. Python documents that its sort is stable. A stable sort keeps the original order of items that have equal keys. The eleven-meeting set has two meetings that end at 9: (3, 9) and (5, 9). They stay in the order they were typed, which is why (3, 9) comes before (5, 9) in the sorted output above.

Python calls the key function once for each meeting. It does not call it once for each comparison. A key that is slow to compute therefore costs one call per meeting. The sort itself makes about n log n comparisons, where n is the number of meetings. In the worst case, the time is O(n log n).

Keys, and the older comparator style

In Python you give the sort a key function. For each item, the key function returns the value to compare. Python does the comparing. The key lambda m: m[1] says: compare meetings by their end. A key function is the normal way to sort in Python.

Some code and some problems use a comparator instead. A comparator is a function that takes two items and returns a negative number when the first comes first, zero when they are equal, and a positive number when the second comes first. The function functools.cmp_to_key turns a comparator into a key, so both styles work with sorted.

If you have seen Java, a key function does the job that a Java comparator does in Arrays.sort, with less code.

Integers do not overflow

Many languages store integers in a fixed number of bits, so a subtraction can wrap around past the largest value. Python integers have no fixed size, so a - b gives the exact difference for any size. The program below shows that a comparator with subtraction sorts correctly here. It also shows the key style, which is the one to use by default.

Output:

big - negative = 4000000000
type: int
sorted with a - b: [-2000000000, 0, 2000000000]
sorted with key:   [-2000000000, 0, 2000000000]

The first line is the exact difference, 4000000000. The rule for this course is simple. Sort with key=. Use cmp_to_key only when the problem needs a comparator, and make the comparator return a negative number, zero or a positive number.

Worked example 2: a rule that wins on one input and loses on another

Activity selection has many natural rules, and it is easy to pick the wrong one. The next program runs three rules on the same three meetings and prints each count. It is a good template for testing a rule on your own inputs.

The function greedy takes the meetings and a key function. It sorts with sorted, which makes a new list, so the caller's list is not changed. Passing the rule as a parameter means you do not need to copy the loop for each rule.

Output:

earliest end:   2
earliest start: 2
shortest first: 1
long case, earliest start: 1
long case, earliest end:   2

Trace the shortest-first result by hand, because that is the point of the example. The lengths are 4, 3 and 5. The sorted order by length is (3, 6), (0, 4), (5, 10). The first meeting taken is (3, 6), so last_end becomes 6. Next, (0, 4) starts at 0, which is before 6, so it is skipped. Then (5, 10) starts at 5, which is also before 6, so it is skipped. The count is 1.

The best possible answer is 2, for example (0, 4) and (5, 10). So shortest-first is wrong. The earliest-end and earliest-start rules both gave 2 on this input, but earliest start is not safe in general, as the long-meeting case showed. A single test can make a wrong rule look right. Test several cases before you trust a rule.

Worked example 3: back-to-back and overlapping meetings

Two edge cases appear in almost every interview about this topic. They test whether you understand the overlap rule and the sort.

Back-to-back meetings. Take (0, 2), (2, 4) and (4, 6). Sorted by end, the order does not change. Take (0, 2), so last_end is 2. The meeting (2, 4) starts at 2. The check 2 >= 2 is true, so it is taken, and last_end becomes 4. The meeting (4, 6) starts at 4, and 4 >= 4 is true, so it is taken too. The count is 3. If the check were start > last_end, the meeting (2, 4) would be skipped, and the count would be 2 instead of 3.

Every meeting overlaps. Take (0, 10), (1, 9), (2, 8) and (3, 7). Sorted by end, the order is (3, 7), (2, 8), (1, 9), (0, 10). Take (3, 7), so last_end is 7. Every other meeting starts before 7, so every one is skipped. The count is 1. The rule chose the meeting that ends soonest, and that choice blocked all the others. In this case that is the best possible answer, because all four meetings clash with each other.

Identical end times. Take (0, 5), (4, 5) and (2, 5). All three end at 5. Whichever one is taken first, its end is 5, and the other two start before 5. So the count is 1 in every order. The count does not depend on how ties are broken, but the list of chosen meetings can.

Output:

back to back: 3
every meeting overlaps: 1
identical end times: 1

These examples are small enough to check on paper. Doing that is the fastest way to build confidence in a rule before you test it on large inputs.

Debugging walkthrough: tracing the decisions

When a greedy program gives a surprising answer, print the sorted list and every decision. Most greedy bugs fall into three groups. The sort key is wrong. The comparison uses > where it should use >=. Or last_end is updated in the wrong branch. A trace shows all three at once.

The next program prints the sorted order first. Then it prints one line per meeting, with its start and end, the value of last_end before the decision, and the decision. Read the output as if you were the algorithm.

Output:

sorted by end: (0,4) (3,6) (5,10)
(0,4)  last_end=-inf  take
(3,6)  last_end=4  skip
(5,10)  last_end=4  take

The line (3,6) last_end=4 skip is the key line. It says the meeting starting at 3 overlaps the one that ended at 4. If your own trace shows take on that line, your comparison is wrong. If the sorted line does not show increasing ends, your key is wrong.

The first line shows last_end=-inf. Negative infinity is smaller than any start time, so the first meeting always fits. Choosing the starting value is a small decision, and it is worth stating out loud in an interview.

The method works for every greedy problem in this course. Write the state down at each step, then check each decision by hand. Computers do not make these mistakes. People do, and the trace is how you find them.

Common mistakes and their real messages

These are the mistakes beginners make most often in this topic. Each one has a short explanation of what you see.

Sorting by start time. The program runs, but the count is too small on inputs with one long meeting early in the list. The three-meeting example gives the right answer by luck. Use the (0, 100), (1, 2), (3, 4) example instead, where earliest start gives 1 and the best is 2. The fix is to sort by index 1, the end.

Using > instead of >=. A meeting that starts at the exact moment last_end is rejected, even though it does not overlap. Back-to-back meetings lose their place, and the count drops. The fix is m[0] >= last_end. Test with (0, 2), (2, 4), (4, 6), where the right answer is 3.

Forgetting to update last_end. If you take a meeting but forget to set last_end, every later meeting is compared with an old end. Too many meetings get taken, and the printed list shows overlapping pairs. Print the chosen list to catch this quickly.

Unpacking in the wrong order. If the data stores each meeting as (end, start) but the loop reads start, end = m, every meeting is reversed. The sort then uses the start where it should use the end, and the answer is nonsense. Check the order of the numbers before you unpack them.

Using the result of sort(). list.sort() changes the list and returns None. If you assign its result, the name holds nothing useful:

meetings = [(0, 4), (3, 6), (5, 10)]
result = meetings.sort(key=lambda m: m[1])
print(result[0])

Python prints this error on the last line:

TypeError: 'NoneType' object is not subscriptable

The message means you tried to take an index from None. Use sorted(meetings, key=...) when you want a new list, or call meetings.sort(key=...) and do not assign the result.

Changing a tuple. Tuples cannot be changed after they are made:

meeting = (0, 4)
meeting[0] = 1

TypeError: 'tuple' object does not support item assignment

To change a meeting, make a new tuple, for example meeting = (1, meeting[1]).

Using an index that does not exist. A meeting has indexes 0 and 1 only. Index 2 is outside the tuple:

meetings = [(1, 4), (3, 5)]
print(sorted(meetings, key=lambda m: m[2]))

IndexError: tuple index out of range

A comparator that returns True or False. Python does not raise an error for this mistake. The list simply comes back in the wrong order. The comparator below returns True or False, which Python reads as 1 or 0. It never returns a negative number, so the sort learns nothing.

from functools import cmp_to_key
 
print(sorted([3, 1, 2], key=cmp_to_key(lambda a, b: a > b)))

[3, 1, 2]

The fix is a comparator that returns a negative number, zero or a positive number, such as (a > b) - (a < b). With that comparator the same call prints [1, 2, 3].

Reading text where a number is expected. If the input holds the word abc and the program calls int on it, Python stops with a ValueError:

start = int("abc")

ValueError: invalid literal for int() with base 10: 'abc'

The line before the message shows which line of your code failed. Read the last line first. It names the problem.

If a program calls input() more times than the input has lines, Python raises EOFError. EOF stands for end of file. The message is:

EOFError: EOF when reading a line

Forgetting the import. A module such as math is not available until you import it. Without the import, Python stops with a NameError:

print(math.floor(2.5))

NameError: name 'math' is not defined. Did you forget to import 'math'?

The fix is to add import math at the top of the file.

Mixing text and numbers in one sort. If one start is text and another is a number, the sort cannot compare them:

print(sorted([(1, 4), ("3", 5)]))

TypeError: '<' not supported between instances of 'str' and 'int'

The usual cause is a value read from input without int(). Convert each number as you read it.

Trusting a rule because one example passed. This is not a Python error message, but it is the most common cause of wrong answers in interviews. Always test a rule on a small tricky case before you write the final code. The three-meeting example is a good first test.

Variations and edge cases

Interviewers like to change the problem a little to see whether you understand the idea. Here are common variations and what changes in each.

• Zero meetings. If the list is empty, the loop never runs, and the answer is 0. greedy([], key) returns 0.
• One meeting. The answer is 1. The first meeting always fits because last_end starts below any valid start.
• All meetings overlap. The answer is 1, as shown in worked example 3. The rule takes the earliest-ending meeting, and that blocks the rest.
• Back-to-back meetings. All of them fit when each starts exactly when the previous one ends. The >= check handles this.
• Ties in end time. The count is the same in any order, but the printed list can change. Python's sort keeps tied meetings in input order, so the output is predictable. If the problem asks for a particular list, decide on a tie-break rule and state it.
• Minimum removals. A common variant asks for the fewest meetings to remove so that the rest do not overlap. The answer is n minus the largest count you can keep. The greedy rule gives the largest count, so the removals follow directly.
• Zero-length meetings. A meeting with start equal to end takes no time. Most problem statements say start is less than end. If the statement allows equal values, the greedy rule still gives a valid answer, but you should say so in an interview.

The same idea works in other problems. Balloons on a wall can be seen as intervals on a line. An arrow shot at position x pops every balloon whose interval contains x. The fewest arrows come from sorting the balloons by their right end, then shooting each new arrow at that end whenever the next balloon is not yet popped. The structure is the same as activity selection, so the same sort key works. Interviewers use this kind of transfer question to check whether you understand the idea or only remember the code.

Complexity, stated carefully

For n meetings:

• Time: O(n log n). The sort dominates. The greedy loop is O(n).
• Extra space: O(1) for the loop variables. The sort may use more. Python's sort can need up to O(n) extra space for its merges.

When you explain this in an interview, say the sort first and the loop second. Then say which part dominates. Keep the answer short, because the interviewer will ask follow-up questions if they want more detail.

Interview questions you should be ready for

1. What is the greedy rule, and why is it safe? Sort by end time. Take each meeting that starts at or after the end of the last one taken. It is safe because of the exchange argument in lesson 4. Any best schedule can swap its first meeting for the earliest-ending one without losing a meeting.
2. Why not sort by start time? A long meeting that starts early can block many short ones. Give the example (0, 100), (1, 2), (3, 4), where earliest start gives 1 and the best is 2.
3. What is the difference between this and the meeting rooms problem? Activity selection asks for the largest set of meetings that fit in one room. Meeting rooms asks for the fewest rooms needed to hold all the meetings. The second problem uses a different method, usually a heap, which is covered in the heaps lesson.
4. How would you return the chosen meetings, not just the count? Keep the chosen pairs in a list as you go, as the first program does with chosen.
5. What if two meetings end at the same time? The count is the same in any order. The chosen list can differ, so state your tie-break rule.

Real-world uses

Activity selection appears in booking systems. A clinic that has one examination room wants the largest number of appointments from a list of requests. It also appears in scheduling a single machine that runs jobs in fixed windows. In both cases the sort key is the end time, because the end is what decides what can come next.

The idea is also a building block. Many larger scheduling problems solve a sub-problem like this one repeatedly, then combine the results. Knowing the greedy version gives you a clear base to build on.

What happens inside the loop

It helps to look at the loop as the computer runs it, one step at a time. Start with last_end set to negative infinity. Read the first meeting in sorted order. The check start >= last_end is always true for the first meeting, so it is taken. The variable count becomes 1, and last_end becomes the end of that meeting.

For each later meeting, the check compares one number with one number. There is no list to search and no table to fill. The loop reads the next meeting, makes one comparison, and possibly updates two variables. That is why the greedy loop is so cheap.

The chosen list in the eleven-meeting program is a separate concern. Adding to a list takes a little extra work, but it does not change the decisions. If you only need the count, remove chosen and keep a counter instead. The code gets shorter.

Practice

1. Run the algorithm by hand on (1,3), (2,4) and (3,5). Write the sorted order, each decision and the count. Then put these three meetings into the eleven-meeting program in place of its list, and run it. The answer is 2.

Show the answer

Sorted by end: (1,3), (2,4), (3,5). Take (1,3), so last_end is 3. (2,4) starts at 2, which is before 3, so skip it. (3,5) starts at 3, which is not before 3, so take it. The count is 2.

2. Find three meetings where earliest start first gives a smaller count than earliest end first. Hint: put one long meeting at the start that covers two short ones after it.

Show the answer

One example is (0,10), (1,3), (4,6). Earliest start takes (0,10) first, which blocks the other two, so the count is 1. Earliest end takes (1,3) and (4,6), so the count is 2.

3. Explain in two sentences why m[0] >= last_end is correct and m[0] > last_end is wrong. Use the back-to-back pair (0, 2) and (2, 4) as your example.

Show the answer

With >=, a meeting that starts exactly when the last one ends is allowed, so (0,2) and (2,4) are both taken. With >, the start 2 is not greater than the end 2, so (2,4) is wrongly skipped. The count drops from 2 to 1.

4. Change the eleven-meeting program so it also prints the number of meetings skipped. Predict the number before you run it.

Show the answer

Count the skipped meetings as the number of meetings minus the number taken. For the eleven-meeting set, 4 meetings are taken, so 7 are skipped. Your output should show 7. A line such as print("skipped:", len(meetings) - len(chosen)) prints it.

5. Write a key function for meetings that sorts by length, and by end time when two lengths are equal. Test it on (0,4), (2,6) and (1,3). The sorted order should be (1,3), (0,4), (2,6).

Show the answer

Use a key that returns a tuple: the length first, then the end.

ordered = sorted(meetings, key=lambda m: (m[1] - m[0], m[1]))

Python compares tuples one element at a time. On (0,4), (2,6) and (1,3), the lengths are 4, 4 and 2. The sorted order is (1,3), (0,4), (2,6).

6. Give an example with two different valid choices of meetings that have the same count. Hint: use two meetings that end at the same time.

Show the answer

Take (0,6), (3,6) and (6,9). Sorted by end, the first two tie, and Python keeps them in input order. Taking (0,6) then (6,9) gives 2 meetings. Taking (3,6) then (6,9) also gives 2. The count is the same, but the chosen list differs.

7. What does the program print for three copies of the meeting (4,4)? Explain using the rule start >= last_end, and say whether the problem should allow zero-length meetings.

Show the answer

Each (4,4) has start equal to end, so it takes no time. The first one sets last_end to 4. Each later one has start 4, and 4 >= 4 is true, so all three are taken. The program prints 3. Whether that is right depends on the problem. Most statements require start to be less than end, so you should say so in an interview.

8. Compute the answer for (0,2) (2,4) (4,6) (1,3) by hand. Then run the greedy function with that list and compare.

Show the answer

Sorted by end: (0,2), (1,3), (2,4), (4,6). Take (0,2), last_end 2. Skip (1,3). Take (2,4), last_end 4. Take (4,6). The answer is 3.

9. The balloon problem uses closed intervals, where an arrow at the end of a balloon pops it. Explain why sorting by the right end is the right choice there too.

Show the answer

Balloons are closed intervals. Sorting by the right end means the arrow lands as early as possible, so it covers the most balloons that start before it. Shooting at the right end of the first unpopped balloon never misses a balloon that a later arrow would need to reach. The reasoning is the same as the activity selection argument, with an arrow in place of a meeting.

10. A friend says: "Just sort by duration and take the shortest meetings first. It is simpler." Write a reply that uses one counterexample to show why this is wrong.

Show the answer

Use (0,4), (3,6), (5,10). Shortest first takes (3,6), which has length 3, and then blocks both others. It gets 1. The best is 2, from (0,4) and (5,10). A short meeting in the middle of two longer ones is the usual trap.

What you now know

• A greedy algorithm makes one locally best choice at a time and never revisits it.
• A greedy rule is only a solution once you can prove it is safe.
• Activity selection is solved by sorting on end time and taking each meeting that starts at or after the last end.
• Use >= for the overlap check, sort with a key function, and trace the decisions whenever a result looks wrong.
• The sort dominates the running time, which is O(n log n).

Next lesson: fractional knapsack and job sequencing, where the right sort key changes.