Greedy algorithms

Prerequisites

• Sorting.
• The idea of an optimal solution.
• Intervals: start and end times.

The analogy

How it works

When greedy works: the problem must have the greedy-choice property (some optimal solution starts with the greedy choice) and optimal substructure (the rest is again an optimal solution of a smaller problem).

Start with activity selection by hand

Talks sorted by end time: A 1–3, B 2–5, C 4–6, D 6–8, E 5–9, F 8–10. Keep a talk if it starts no earlier than the last kept talk ends. Predict, then open "Check".

Finish the picture: when greedy fails

Make change for 6 with coins {1, 3, 4}, greedily taking the biggest coin that fits.

• The greedy answer. Predict the coins.
  Check

  4, then 1, then 1: three coins.

• The best answer. Predict it, and say what greedy got wrong.
  Check

  3 + 3: two coins. Taking 4 first looked best but left 2, which only 1s can pay. Greedy never reconsiders, so it can't recover.

The rule in plain words

Sort or order the candidates by a greedy rule (here: earliest finish). Go through them once; take each candidate that keeps the solution valid and never undo a choice.

Before trusting it, prove the rule is safe (an exchange argument) or test it against counter-examples.

The code

Read this code after you have selected the talks by hand. It will make more sense.

int select_activities(int start[], int end[], int n, int chosen[]) {   /* sorted by end */
    int k = 0, last_end = -1;
    for (int i = 0; i < n; i++)
        if (start[i] >= last_end) {        /* fits after the last kept talk */
            chosen[k++] = i;
            last_end = end[i];             /* earliest finish so far */
        }
    return k;                              /* how many talks were kept */
}

flowchart TD
  A["sort talks by end time"] --> B["take the next talk"]
  B --> C{"starts after the last kept talk ends?"}
  C -->|yes| D["keep it, update last end"]
  C -->|no| E["skip it"]
  D --> F{"more talks?"}
  E --> F
  F -->|yes| B
  F -->|no| G["done: maximum number of talks"]
          

How fast is it?

Sorting the $n$ talks dominates; the selection itself is one pass:

Common mistakes

• Assuming greedy is optimal without a proof.
• Sorting by the wrong key (start time or duration instead of end time).
• Using greedy for 0/1 knapsack or arbitrary coin systems, where dynamic programming is needed.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Greedy is fast because it makes one pass without ever backtracking.
• Earliest finish is safe because it leaves the most time for the remaining talks.
• Greedy can fail because a choice that looks best now can block a better combination later.
• A proof is needed because correctness depends on the greedy-choice property, which many problems lack.
• Sorting usually dominates because the selection pass itself is linear.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a greedy algorithm like packing a bag by always grabbing the most useful thing that fits?
   Sample answer

   Each step takes the locally best option and never reconsiders, which is fast but can miss a better overall combination.

2. Walk through activity selection on A 1–3, B 2–5, C 4–6, D 6–8, E 5–9, F 8–10.
   Sample answer

   Keep A; skip B (starts at 2); keep C; keep D; skip E (starts at 5); keep F. Four talks: A, C, D, F.

3. Why does the code compare start[i] >= last_end?

   A good answer says what last_end holds.

   Sample answer

   last_end is when the last kept talk ends; a talk starting at or after it doesn't overlap, so it can be kept.

4. So what is a greedy algorithm, in one sentence?
   Sample answer

   An algorithm that builds a solution step by step by always taking the locally best choice and never revising it.

5. Why is "earliest finish first" optimal for activity selection?

   A good answer uses an exchange argument.

   Sample answer

   Take any optimal schedule and replace its first talk with the earliest-finishing one: it ends no later, so it can't clash with the rest. Repeating the argument shows greedy keeps as many talks.

6. What does activity selection cost?
   Sample answer

   $O(n \log n)$ for sorting by end time, plus $O(n)$ for the selection pass.

7. Give a problem where greedy fails, and what to use instead.
   Sample answer

   Change for 6 with coins {1, 3, 4}: greedy gives 4 + 1 + 1, the best is 3 + 3. Dynamic programming finds the true optimum.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the formal properties and fractional knapsack. I'd keep the bag analogy, the talk-scheduling example, the coin counter-example, and "fast, but only optimal when you can prove it".

External resources

• GeeksforGeeks: Activity selection: the problem, proof and code.
• Wikipedia: Greedy algorithm: when greedy works and classic failures.
• MIT OCW 6.046J Design and Analysis of Algorithms: lectures on greedy algorithms and their proofs.

Videos

• YouTube search: greedy activity selection: pick a walkthrough with a timeline.