Greedy Algorithms: Local Optimal Choices

Picture yourself at a stationery shop near your school. You buy a geometry box and a notebook worth ₹163, and you hand the shopkeeper a ₹200 note. She needs to return ₹37 in change. Without pausing to think hard, she reaches for a ₹20 note, then a ₹10 note, then a ₹5 coin, then a ₹2 coin — four pieces of currency, handed over in one confident pass, never taking any of them back. She did not sit down and compare every possible combination of notes and coins that could add up to ₹37. She simply picked the biggest note or coin that was still less than or equal to what was owed, at every single step, and moved on. That instinctive shortcut has a formal name in computer science: a greedy algorithm. This chapter is about understanding exactly what that shortcut is, why it works beautifully in some situations and fails badly in others, and how to tell the difference — a distinction that trips up even confident programmers if they treat "greedy" as a magic word instead of a method with real, checkable conditions.

Making Change the Way a Cashier Does

Let us make the shopkeeper's method precise enough to turn into code. Indian currency comes in a standard set of denominations: ₹500, ₹200, ₹100, ₹50, ₹20, ₹10, ₹5, ₹2, and ₹1. Suppose we need to hand back ₹93 in change, using as few notes and coins as possible. The greedy method is: look at the largest denomination that is not bigger than the remaining amount, use it, subtract it from what is owed, and repeat until nothing is left.

Let us trace it by hand for ₹93:

• Remaining ₹93. Largest denomination ≈ ₹93 is ₹50. Use it. Remaining becomes ₹43.
• Remaining ₹43. ₹50 is too big now. Largest that fits is ₹20. Use it. Remaining becomes ₹23.
• Remaining ₹23. ₹20 still fits. Use it again. Remaining becomes ₹3.
• Remaining ₹3. ₹10 and ₹5 are too big. Largest that fits is ₹2. Use it. Remaining becomes ₹1.
• Remaining ₹1. Use ₹1. Remaining becomes ₹0. Done.

Total notes and coins used: one ₹50, two ₹20s, one ₹2, one ₹1 — five pieces altogether. If you try to beat this by hand with any other combination that sums to ₹93, you will not find one that uses fewer than five pieces. The greedy method, in this case, happens to land on the truly best possible answer, and it did so without ever exploring another path or reconsidering a choice once made.

Here is that same logic as a Python function, which is how you would write it for a CBSE Informatics Practices lab record:

def make_change(amount, denominations):
    denominations = sorted(denominations, reverse=True)
    notes_used = []
    for coin in denominations:
        while amount >= coin:
            notes_used.append(coin)
            amount -= coin
    return notes_used

result = make_change(93, [500, 200, 100, 50, 20, 10, 5, 2, 1])
print(result)
# Output: [50, 20, 20, 2, 1]

Trace it line by line to confirm the output. denominations becomes [500, 200, 100, 50, 20, 10, 5, 2, 1] after sorting in reverse. The outer for loop visits each value in that order. At coin = 500, the inner while condition 93 >= 500 is false, so nothing happens; the same is true for 200 and 100. At coin = 50, 93 >= 50 is true, so 50 is appended and amount drops to 43; the while-loop checks again, 43 >= 50 is false, so it exits and moves to the next coin. At coin = 20, 43 >= 20 is true twice in a row (appending 20 twice, amount going 43 → 23 → 3), then 3 >= 20 is false. At coin = 10 and coin = 5, the condition is false immediately. At coin = 2, 3 >= 2 is true once, appending 2, amount becomes 1. At coin = 1, 1 >= 1 is true once, appending 1, amount becomes 0, and every remaining check fails. The final list is exactly [50, 20, 20, 2, 1], matching the hand trace.

Naming the Idea Precisely: What Makes an Algorithm "Greedy"

Every greedy algorithm shares three features, and it is worth pinning them down instead of leaving "greedy" as a vague synonym for "quick and simple."

1. It builds a solution step by step. It does not conjure the final answer in one shot; it adds one piece at a time (one coin, one activity, one item) to a growing partial answer.
2. At every step, it makes the choice that looks best right now, using only local information. The cashier does not know or care what change she will need to give the next customer — she only looks at the ₹93 in front of her at this instant.
3. It never revisits or undoes a choice. Once the ₹50 note is handed over, it is not taken back later even if, for some other target amount, that would have been the smarter move. This is what "greedy" really refers to — it grabs the best-looking option immediately and commits, in contrast to methods that backtrack or that explore multiple branches before deciding.

This last property is exactly what makes greedy algorithms fast. There is no need to store multiple candidate solutions or revisit earlier decisions, so a well-designed greedy algorithm typically runs in the time it takes to sort the input once (commonly O(n log n)) followed by a single linear pass (O(n)) — dramatically faster than checking every possible combination, which can take time that grows exponentially with the input size. But that speed comes with a serious catch, and understanding the catch is the real point of this chapter.

The Trap: "Greedy" Does Not Automatically Mean "Correct"

A very common misconception among students meeting this topic for the first time is: "Greedy algorithms always find the best possible answer, because at every step they pick the best option." This is false, and it is important to see a concrete case where it fails, not just be told it can fail.

Suppose a fictional currency system had only three denominations: ₹1, ₹3, and ₹4 (this is not real Indian currency — it is a deliberately different set, chosen to break the pattern). We want to make ₹6 using as few coins as possible.

The greedy method picks the largest coin that fits, every time:

• Remaining ₹6. Largest that fits: ₹4. Use it. Remaining ₹2.
• Remaining ₹2. ₹4 and ₹3 are too big. Largest that fits: ₹1. Use it. Remaining ₹1.
• Remaining ₹1. Use ₹1. Remaining ₹0.

Greedy's answer: ₹4 + ₹1 + ₹1 = three coins. But look at ₹3 + ₹3 = ₹6 — only two coins. Greedy's locally sensible choice of grabbing the ₹4 coin first actually locked it into a worse total, because after removing ₹4 it was stuck patching the remaining ₹2 with two separate ₹1 coins, while a less "greedy-looking" first move of ₹3 left a remaining ₹3 that could be finished in a single additional coin.

Running the exact same make_change function from earlier with denominations = [4, 3, 1] and amount = 6 confirms this on the machine: the loop takes coin = 4 first (since it is largest and sorted first), 6 >= 4 is true, appends 4, amount becomes 2; then coin = 3, 2 >= 3 is false, skip; then coin = 1, appends 1 twice as amount goes 2 → 1 → 0. Output: [4, 1, 1], three coins — provably not the fewest possible.

Why did greedy work perfectly for real Indian denominations but fail for {₹1, ₹3, ₹4}? The honest, precise answer is: it depends on the specific structure of the denomination set, and there is no simple one-line rule that always predicts it correctly for every arbitrary set of denominations — each such currency system genuinely needs to be checked or proven. What we can say confidently is that the standard Indian note-and-coin system (₹1, ₹2, ₹5, ₹10, ₹20, ₹50, ₹100, ₹200, ₹500) has been verified to make the greedy method always produce the minimum number of notes and coins for any amount, which is precisely why cashiers everywhere can trust their instinct without doing any deeper calculation. But that guarantee comes from the properties of this particular set of numbers, not from "greedy algorithms in general."

When Greedy Provably Works: The Activity Selection Problem

To see greedy succeed for a deeper, provable reason (not just because a particular currency happens to cooperate), consider a scheduling problem that is one of the cleanest and most famous in all of computer science.

It is Sunday, and you have six subject revision sessions available before your CBSE exams, each with a fixed start and end hour, and each led by the same tutor, so you can attend only one at a time — if two overlap even slightly, you must skip one of them entirely. You want to attend the maximum number of non-overlapping sessions possible. The sessions are:

• English: 0 to 2
• Math: 1 to 4
• Science: 3 to 5
• Social Science: 5 to 7
• Hindi: 6 to 8
• Computer Science: 8 to 9

This is the classic activity selection problem. The greedy strategy that solves it optimally is surprisingly simple, and surprisingly different from "pick the biggest thing" — here, "biggest" would be the wrong instinct entirely. The correct rule is: always sort the sessions by their finishing time, and greedily pick the next session whose start time is not earlier than the finish time of the last session you picked. Finishing early, not starting early or lasting long, is the property that matters, because a session that ends sooner leaves more of the day free for whatever comes after it.

Sorted by finish time, the list is already in the order shown above: English (ends 2), Math (ends 4), Science (ends 5), Social Science (ends 7), Hindi (ends 8), Computer Science (ends 9). Now walk through it:

• Pick English (0–2) — it is first in line, always take the first one after sorting. Last end time is now 2.
• Check Math (1–4): its start, 1, is before 2, so it overlaps English. Reject it.
• Check Science (3–5): its start, 3, is not before 2. It is compatible. Pick it. Last end time is now 5.
• Check Social Science (5–7): its start, 5, is not before 5. Compatible (they meet exactly at the boundary, which counts as non-overlapping). Pick it. Last end time is now 7.
• Check Hindi (6–8): its start, 6, is before 7. Overlaps. Reject it.
• Check Computer Science (8–9): its start, 8, is not before 7. Compatible. Pick it. Last end time is now 9.

Final selection: English, Science, Social Science, Computer Science — four sessions. Checking by hand against every other way of avoiding overlaps among these six sessions confirms that four is in fact the maximum achievable; no combination of five of them is mutually non-overlapping, because Math always collides with English, and Hindi always collides with Social Science, whichever other choices you make around them. Unlike the currency example, this is not a lucky coincidence of the specific numbers — the earliest-finish-time greedy rule is provably optimal for this problem for any set of intervals whatsoever, for a reason we can explain in plain language.

Why it always works (the exchange argument, in simple terms): imagine any correct, optimal schedule that does not start by picking the session with the very earliest finish time. That optimal schedule must start with some other session instead. But swap that first session out and replace it with the earliest-finishing one — since the earliest-finishing session ends no later than whatever it replaced, every session that came after in the original schedule is still perfectly compatible with this swap. So the swap never costs you anything and never breaks the schedule, meaning there is always an equally good optimal schedule that does start with the earliest-finishing session. The same argument then reapplies to the remaining sessions, one step at a time. That is the precise, checkable reason the greedy choice is safe here — not a hope, not a pattern that happened to work on one example, but a guarantee that holds for every possible input.

Here is the diagram of the trace above, showing exactly which sessions the greedy pass keeps and which it discards, and why:

Here is the corresponding Python code. Trace it against the diagram to see that every line matches a step you already walked through by hand:

def select_activities(activities):
    # Step 1: sort by finish time (the second value in each tuple)
    activities = sorted(activities, key=lambda a: a[1])
    selected = [activities[0]]
    last_end = activities[0][1]
    for start, end in activities[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

sessions = [(0, 2), (1, 4), (3, 5), (5, 7), (6, 8), (8, 9)]
print(select_activities(sessions))
# Output: [(0, 2), (3, 5), (5, 7), (8, 9)]

Tracing this: after sorting, activities is unchanged since the list was already ordered by end time. selected starts as [(0, 2)] and last_end = 2. The loop then examines (1, 4): is 1 >= 2? No, skipped. Next, (3, 5): is 3 >= 2? Yes — append it, last_end becomes 5. Next, (5, 7): is 5 >= 5? Yes — append it, last_end becomes 7. Next, (6, 8): is 6 >= 7? No, skipped. Next, (8, 9): is 8 >= 7? Yes — append it, last_end becomes 9. Final selected list: exactly the four tuples shown, matching the hand trace and the diagram.

The General Greedy Algorithm Template

Both examples in this chapter followed the same four-part recipe, and recognizing this recipe is what lets you design your own greedy algorithms instead of only recognizing the two shown here:

1. Identify the sequence of decisions your algorithm needs to make (which coin to hand over next; which activity to accept or reject next).
2. Choose a ranking rule that measures "how good" each candidate looks locally, and sort or order candidates by it (largest denomination first; earliest finish time first). Choosing the right ranking rule is the hardest and most important part of designing a correct greedy algorithm — notice that "largest denomination" worked for currency but "earliest finish" (not "shortest duration" or "earliest start") was the rule that worked for scheduling. A wrong ranking rule silently produces a wrong answer that still looks reasonable, which is exactly what happened with {₹1, ₹3, ₹4}.
3. Walk through candidates in ranked order, accepting each one only if it keeps the solution feasible (the coin does not overshoot the remaining amount; the activity does not overlap what is already chosen).
4. Never look back. Once a candidate is accepted or rejected, that decision is permanent for the rest of the run.

This is also why greedy algorithms are attractive whenever they do apply: step 3 is typically a single pass through the sorted candidates, so the total work is dominated by the sort itself. Compare this to a brute-force method that tried every possible subset of six activities to find the best combination — with six activities there are 2⁶ = 64 subsets to check, and this number doubles with every additional activity added. For a real school timetable with thirty possible sessions, brute force would mean checking over a billion combinations, while the greedy method still finishes after one sort and one pass through the list.

How to Actually Tell Whether Greedy Will Work

Given the currency counter-example, it would be reasonable to worry that greedy algorithms are unreliable in general and should be avoided. The right lesson is narrower and more useful: greedy is trustworthy exactly when a problem has what computer scientists call the greedy choice property — a guarantee, provable for that specific problem, that making the locally best choice first never rules out reaching a globally best final answer. The activity selection problem has this property, and the exchange argument above is the proof. The {₹1, ₹3, ₹4} currency problem does not have this property, and the three-coins-versus-two-coins example is the disproof. Whether a given problem has this property is not something you can guess from the problem's description alone — it has to be established, either by a proof like the exchange argument, or by checking known results for that exact problem. This is precisely why, later in your study of algorithms, you will meet problems like the general coin-change problem (with arbitrary denominations) solved instead using dynamic programming, a method that does look back and reconsider earlier choices in order to guarantee correctness even when no greedy shortcut is provably safe.

Practice: Test Your Understanding

1. Using the standard Indian denominations and the same greedy method traced earlier, hand-trace make_change(163, [500, 200, 100, 50, 20, 10, 5, 2, 1]). List every note and coin used, in order.

Check yourself: ₹100, then ₹50 (remaining drops to 13), then ₹10 (remaining 3), then ₹2, then ₹1 — five pieces total: 100, 50, 10, 2, 1.

2. A fictional currency has denominations {1, 5, 6}. Using the greedy method, make ₹10. Then find a non-greedy combination that uses fewer coins, and explain in one sentence why greedy failed here.

Check yourself: Greedy picks 6, then four separate 1s: five coins total (6, 1, 1, 1, 1). But 5 + 5 = 10 uses only two coins. Greedy failed because grabbing the ₹6 coin first left a remainder of ₹4 that could not be finished efficiently, whereas the less "greedy-looking" first pick of ₹5 left a remainder that matched a denomination exactly.

3. You have five coaching sessions with start/end hours: (2, 4), (1, 3), (3, 6), (5, 8), (7, 9). Using the earliest-finish-time greedy rule, which sessions get selected, and how many is that in total?

Check yourself: Sorted by finish time: (1,3), (2,4), (3,6), (5,8), (7,9). Pick (1,3), last_end=3. Reject (2,4) since 2<3. Pick (3,6) since 3≥3, last_end=6. Reject (5,8) since 5<6. Pick (7,9) since 7≥6. Final: (1,3), (3,6), (7,9) — three sessions, and this is the maximum possible for this set.

4. True or False, with a reason: "If a greedy algorithm gives the correct, optimal answer on three example inputs you tried by hand, it is safe to assume it will be correct on every possible input."

Check yourself: False. Correctness on a handful of examples never proves correctness for all inputs — the {₹1, ₹3, ₹4} example matched the greedy pattern in structure to real currency but broke it on a target of ₹6. Only a genuine argument (like the exchange argument for activity selection) or an exhaustive proof for the specific problem's structure establishes that a greedy method always works.

Summary

A greedy algorithm builds a solution one decision at a time, always taking whichever available option looks best by some chosen ranking rule at that exact moment, and never revisiting a decision once made. This makes greedy algorithms fast — typically one sort plus one linear pass — which is a real and valuable advantage over checking every possible combination. The Indian currency change-making problem and the activity selection problem both show greedy at its best, producing the true optimal answer efficiently. But greedy is a method with conditions attached, not a guarantee: the {₹1, ₹3, ₹4} example proves that a locally sensible first choice can permanently rule out the best overall answer. A greedy algorithm can be trusted only when the specific problem has been shown to have the greedy choice property — proven, for instance, through an exchange argument like the one given for activity selection, which shows that swapping in the locally best choice never makes the final answer worse. Knowing this distinction — between "greedy happened to work here" and "greedy is provably correct here" — is what separates a programmer who got lucky from one who actually understands the algorithm.