Greedy Algorithms: How They Work and How to Prove Them

A cashier giving ₹80 in change hands over a ₹50 note, then a ₹20, then a ₹10: at each step, the largest note that still fits. Nobody plans the whole answer in advance, and nobody takes a note back. That is a greedy algorithm: build the solution one step at a time, take the choice that looks best at that moment, and never revisit it.

Greedy solutions are short and fast, often a sort and one loop. The difficulty is that they are just as short when they are wrong — the cashier's rule fails for coins of 1, 3 and 4 — so the skill has two halves: finding the right rule, and proving it before you trust it.

Why trying every choice is too slow

Take activity selection: one meeting room and a list of meetings, each with a start and an end time. What is the largest number of meetings the room can hold without overlaps? The safe approach tries every subset — 2ⁿ of them, about a million for 20 meetings and 10¹⁵ for 50. Dynamic programming does better, but greedy does better still: sort by end time and sweep once, O(n log n), provably optimal.

The idea: take the best step now, never look back

A greedy algorithm has three parts:

• A rule for the next choice: the meeting that ends first, the largest coin that fits, the jump that reaches farthest.
• A commitment: once made, a choice is final. No backtracking is what makes greedy fast.
• A smaller problem left over, to which the same rule applies.

The simplest example is Jump Game: each nums[i] is the longest jump from index i — can you reach the last index? Walk left to right keeping one number, reach, the farthest index any jump so far can land on. Every index up to it is reachable, since a shorter jump is always allowed; nothing else about the past matters.

1. reach is the farthest index known to be reachable. It starts at 0, where we stand; every index up to reach can be landed on, and nothing past it is known to be reachable yet.
2. From index 0 a jump of up to 1 lands as far as 1, so reach = 1. Shorter jumps land inside the stretch already covered, which is why only the farthest point matters.
3. Index 1 is within reach, and from it a jump of 3 lands at 4, so reach grows to 4: every index from 0 to 4 is now reachable.
4. nums[2] = 0 goes nowhere, but that is no trap: reach is already 4, so index 3 is still reachable and the scan carries on.
5. nums[3] = 0 adds nothing either, since 3 + 0 = 3 is behind reach = 4; a zero only traps the scan when reach stops at it.
6. From index 4 a jump of 2 lands at 6, the last index, so reach = 6 covers the end and the scan can stop.
7. The end is reachable, so the answer is true: 0 → 1 → 4 → 6 works, using the jumps that pushed reach forward. Had i ever passed reach, it would be false. One pass and one number kept: O(n) time, O(1) space.

When greedy is correct

A greedy algorithm is correct when the problem has two properties:

• The greedy-choice property: some optimal solution makes the greedy first choice, so the locally best option never loses.
• Optimal substructure: after that choice, an optimal solution of the smaller problem completes an optimal whole.

The first is the one to prove, and two patterns cover almost every interview problem. An exchange argument swaps any optimal solution's choice for the greedy one without making it worse. Greedy stays ahead shows that after every step greedy is at least as far along as any other solution. If you can find neither, compare your greedy with a brute force on small random inputs: greedy bugs are wrong ideas, and only a counterexample shows them.

Activity selection: earliest finish first

Three rules look plausible: take the meeting that starts first, the shortest, or the one that ends first. Two small counterexamples settle it.

1. Earliest start first takes (0,10): it starts first, but it holds the room until 10 and blocks both short meetings. The best is 2, so the rule is wrong.
2. Shortest first takes (4,7), three hours long, but it overlaps both of the others. The best is 2, from the two longer meetings, so this rule is wrong too.
3. Earliest finish on the first example takes (1,2) and (3,4): the long meeting ends last, so it is considered last and skipped. That is the best, 2.
4. Earliest finish on the second example takes (1,5) and (6,10), again the best. It survives both counterexamples because the meeting that ends first leaves the room free the longest.

So sort by end time, and keep every meeting that starts once the room is free. A meeting may start the moment the previous one ends; if a problem says otherwise, change >= to >.

1. The meetings, sorted by end time, one per row (ties by start). The sweep keeps one number: when the room is next free. It starts free at time 0.
2. (1,2) starts at 1, at or after 0, so it fits: take it, and the room is now free from 2. Of all the meetings it ends first, so it leaves the most time for the rest.
3. (3,4) starts at 3, at or after 2, so it fits: take it, and the room is now free from 4.
4. (0,6) starts at 0, before the room is free at 4: it would overlap a meeting already taken, so it is skipped for good.
5. (5,7) starts at 5, at or after 4, so it fits: take it, and the room is now free from 7.
6. (5,9) starts at 5, before the room is free at 7: it would overlap a meeting already taken, so it is skipped for good.
7. (8,9) starts at 8, at or after 7, so it fits: take it, and the room is now free from 9.
8. 4 meetings, (1,2), (3,4), (5,7) and (8,9), and a brute force over all 64 subsets agrees that 4 is the most. One sort and one pass: O(n log n).

Why earliest finish is optimal

Let g be the meeting that ends first, and take any optimal schedule whose first meeting f is not g. Since g ends no later than f, everything after f also starts after g ends, so replacing f with g creates no overlap and keeps the count. Some optimal schedule therefore begins with g, and the same argument applies to what is left. Repeated, it turns any optimal schedule into greedy's:

1. Greedy picks (1,3), (4,6) and (7,9). Take any optimal schedule — this one, (0,4), (4,7) and (8,10), also holds 3 — and suppose it differs from greedy. The exchange argument turns it into greedy's without ever losing a meeting.
2. At position 1 the optimal schedule has (0,4) where greedy has (1,3). Greedy's choice ends no later (3 ≤ 4), because it ends first among the meetings that fit, and the next meeting starts at 4.
3. Swap (0,4) for (1,3): everything after it started at or after 4, so also after 3. No overlap, same count: still optimal, and it agrees with greedy one meeting further.
4. At position 2 the optimal schedule has (4,7) where greedy has (4,6). Greedy's choice ends no later (6 ≤ 7), because it ends first among the meetings that fit, and the next meeting starts at 8.
5. Swap (4,7) for (4,6): everything after it started at or after 7, so also after 6, and (4,6) starts at 4, once the meeting before it has ended at 3. No overlap, same count: still optimal, and it agrees with greedy one meeting further.
6. At position 3 the optimal schedule has (8,10) where greedy has (7,9). Greedy's choice ends no later (9 ≤ 10), because it ends first among the meetings that fit.
7. Swap (8,10) for (7,9): nothing comes after it, and (7,9) starts at 7, once the meeting before it has ended at 6. No overlap, same count: still optimal, and it agrees with greedy one meeting further.
8. After 3 swaps the optimal schedule is greedy's. No swap lost a meeting, so greedy's schedule is optimal too. That is the exchange argument, and it is the proof to look for before trusting any greedy rule.

The intuition worth keeping: the meeting that finishes first leaves the room free the longest for everything else.

The code

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Meeting {
    int start, end;
};

string show(const Meeting& m) { return "(" + to_string(m.start) + "," + to_string(m.end) + ")"; }

// Most meetings one room can hold: always take the one that ends first.
int maxMeetings(vector<Meeting> meetings) {
    sort(meetings.begin(), meetings.end(), [](const Meeting& a, const Meeting& b) {
        if (a.end != b.end) return a.end < b.end;      // earliest finish first
        return a.start < b.start;                      // ties in a fixed order
    });
    cout << "sorted by end:";
    for (const Meeting& m : meetings) cout << " " << show(m);
    cout << "\n";
    int count = 0, freeAt = 0;                         // the room is free from time 0
    for (const Meeting& m : meetings) {
        if (m.start >= freeAt) {                       // fits after the last meeting taken
            cout << "take " << show(m) << "\n";
            count++;
            freeAt = m.end;
        } else {
            cout << "skip " << show(m) << ": starts before " << freeAt << "\n";
        }
    }
    return count;
}

int main() {
    vector<Meeting> meetings = {{5, 9}, {1, 2}, {5, 7}, {0, 6}, {8, 9}, {3, 4}};
    int best = maxMeetings(meetings);                  // prints its trace first
    cout << "most meetings: " << best << "\n";
    return 0;
}

import java.util.Arrays;

public class Main {
    static String show(int[] m) {
        return "(" + m[0] + "," + m[1] + ")";
    }

    // Most meetings one room can hold: always take the one that ends first.
    static int maxMeetings(int[][] meetings) {
        int[][] sorted = meetings.clone();
        Arrays.sort(sorted, (a, b) -> a[1] != b[1]
                ? Integer.compare(a[1], b[1])          // earliest finish first
                : Integer.compare(a[0], b[0]));        // ties in a fixed order
        StringBuilder line = new StringBuilder("sorted by end:");
        for (int[] m : sorted) line.append(" ").append(show(m));
        System.out.println(line);
        int count = 0, freeAt = 0;                     // the room is free from time 0
        for (int[] m : sorted) {
            if (m[0] >= freeAt) {                      // fits after the last meeting taken
                System.out.println("take " + show(m));
                count++;
                freeAt = m[1];
            } else {
                System.out.println("skip " + show(m) + ": starts before " + freeAt);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] meetings = {{5, 9}, {1, 2}, {5, 7}, {0, 6}, {8, 9}, {3, 4}};
        int best = maxMeetings(meetings);
        System.out.println("most meetings: " + best);
    }
}

def show(m):
    return f"({m[0]},{m[1]})"


def max_meetings(meetings):
    """Most meetings one room can hold: always take the one that ends first."""
    ordered = sorted(meetings, key=lambda m: (m[1], m[0]))   # earliest finish; ties by start
    print("sorted by end:", " ".join(show(m) for m in ordered))
    count, free_at = 0, 0                      # the room is free from time 0
    for m in ordered:
        if m[0] >= free_at:                    # fits after the last meeting taken
            print("take", show(m))
            count += 1
            free_at = m[1]
        else:
            print(f"skip {show(m)}: starts before {free_at}")
    return count


meetings = [(5, 9), (1, 2), (5, 7), (0, 6), (8, 9), (3, 4)]
best = max_meetings(meetings)
print("most meetings:", best)

const show = (m) => `(${m[0]},${m[1]})`;

// Most meetings one room can hold: always take the one that ends first.
function maxMeetings(meetings) {
  // earliest finish first; ties in a fixed order
  const sorted = meetings.slice().sort((a, b) => a[1] - b[1] || a[0] - b[0]);
  console.log(`sorted by end: ${sorted.map(show).join(" ")}`);
  let count = 0;
  let freeAt = 0; // the room is free from time 0
  for (const m of sorted) {
    if (m[0] >= freeAt) {
      // fits after the last meeting taken
      console.log(`take ${show(m)}`);
      count++;
      freeAt = m[1];
    } else {
      console.log(`skip ${show(m)}: starts before ${freeAt}`);
    }
  }
  return count;
}

const meetings = [[5, 9], [1, 2], [5, 7], [0, 6], [8, 9], [3, 4]];
const best = maxMeetings(meetings);
console.log(`most meetings: ${best}`);

sorted by end: (1,2) (3,4) (0,6) (5,7) (5,9) (8,9)
take (1,2)
take (3,4)
skip (0,6): starts before 4
take (5,7)
skip (5,9): starts before 7
take (8,9)
most meetings: 4

The same rule, turned round, solves Non-overlapping Intervals: the fewest intervals to remove is n minus the most you can keep. The whole family is the subject of the intervals lesson.

Jump Game II: the fewest jumps

Jump Game II asks for the fewest jumps to the last index. Now the choice matters, and the obvious greedy — always jump as far as possible — is wrong. The right greedy thinks in levels: the indices reachable with exactly k jumps form one contiguous range, and the next range ends at the farthest landing from it.

1. nums[i] is the longest jump from index i. What is the fewest jumps from index 0 to index 4? The tempting rule — always jump as far as you can — is wrong.
2. Jumping as far as possible goes 0 → 2 → 3 → 4: from 0 the longest jump lands on index 2, whose value 1 is a poor springboard, so it takes 3 jumps.
3. With 1 jump you can stand anywhere from 1 to 2: every index up to the farthest landing (0 + 2 = 2), since a shorter jump is always allowed.
4. From anywhere in the 1-jump range the farthest landing is 4 (1 + 3 = 4, 2 + 1 = 3), so 2 jumps reach indices 3 to 4, which includes the last index: the answer is 2.
5. 2 jumps, for example 0 → 1 → 4. The scan never chooses a jump; it only counts levels, which is "greedy stays ahead": after k jumps, nobody can be beyond the end of level k. Two numbers, one pass: O(n).

The scan keeps end, the last index of the current level, and farthest, the farthest landing from it; when i reaches end, it counts a jump and sets end = farthest. It is a breadth-first search over levels in two numbers, and its proof is "greedy stays ahead". If farthest cannot pass i when a level ends, the end is unreachable.

The code

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Fewest jumps from index 0 to the last index, or -1 if it cannot be reached.
int minJumps(const vector<int>& nums) {
    int n = (int)nums.size();
    int jumps = 0, end = 0, farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        farthest = max(farthest, i + nums[i]);   // best landing point one jump from here
        if (i == end) {                          // the current jump's range is used up
            if (farthest <= i) return -1;        // nothing gets past i: stuck
            jumps++;
            end = farthest;                      // the next level reaches this far
        }
    }
    return jumps;
}

int main() {
    vector<vector<int>> tests = {{2, 3, 1, 1, 4}, {1, 3, 0, 0, 2, 0, 1}, {3, 2, 1, 0, 4}};
    for (const vector<int>& nums : tests) {
        cout << "nums";
        for (int x : nums) cout << " " << x;
        int jumps = minJumps(nums);
        if (jumps == -1) cout << ": the end cannot be reached\n";
        else cout << ": fewest jumps " << jumps << "\n";
    }
    return 0;
}

public class Main {
    // Fewest jumps from index 0 to the last index, or -1 if it cannot be reached.
    static int minJumps(int[] nums) {
        int n = nums.length;
        int jumps = 0, end = 0, farthest = 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);   // best landing point one jump from here
            if (i == end) {                               // the current jump's range is used up
                if (farthest <= i) return -1;             // nothing gets past i: stuck
                jumps++;
                end = farthest;                           // the next level reaches this far
            }
        }
        return jumps;
    }

    public static void main(String[] args) {
        int[][] tests = {{2, 3, 1, 1, 4}, {1, 3, 0, 0, 2, 0, 1}, {3, 2, 1, 0, 4}};
        for (int[] nums : tests) {
            StringBuilder line = new StringBuilder("nums");
            for (int x : nums) line.append(" ").append(x);
            int jumps = minJumps(nums);
            if (jumps == -1) line.append(": the end cannot be reached");
            else line.append(": fewest jumps ").append(jumps);
            System.out.println(line);
        }
    }
}

def min_jumps(nums):
    """Fewest jumps from index 0 to the last index, or -1 if it cannot be reached."""
    n = len(nums)
    jumps, end, farthest = 0, 0, 0
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])   # best landing point one jump from here
        if i == end:                            # the current jump's range is used up
            if farthest <= i:                   # nothing gets past i: stuck
                return -1
            jumps += 1
            end = farthest                      # the next level reaches this far
    return jumps


tests = [[2, 3, 1, 1, 4], [1, 3, 0, 0, 2, 0, 1], [3, 2, 1, 0, 4]]
for nums in tests:
    jumps = min_jumps(nums)
    label = "nums " + " ".join(str(x) for x in nums)
    if jumps == -1:
        print(f"{label}: the end cannot be reached")
    else:
        print(f"{label}: fewest jumps {jumps}")

// Fewest jumps from index 0 to the last index, or -1 if it cannot be reached.
function minJumps(nums) {
  const n = nums.length;
  let jumps = 0;
  let end = 0;
  let farthest = 0;
  for (let i = 0; i < n - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]); // best landing point one jump from here
    if (i === end) {
      // the current jump's range is used up
      if (farthest <= i) return -1; // nothing gets past i: stuck
      jumps++;
      end = farthest; // the next level reaches this far
    }
  }
  return jumps;
}

const tests = [[2, 3, 1, 1, 4], [1, 3, 0, 0, 2, 0, 1], [3, 2, 1, 0, 4]];
for (const nums of tests) {
  const jumps = minJumps(nums);
  const label = `nums ${nums.join(" ")}`;
  if (jumps === -1) console.log(`${label}: the end cannot be reached`);
  else console.log(`${label}: fewest jumps ${jumps}`);
}

nums 2 3 1 1 4: fewest jumps 2
nums 1 3 0 0 2 0 1: fewest jumps 3
nums 3 2 1 0 4: the end cannot be reached

The second test is the array from the walkthrough: 0 to 1, 1 to 4, 4 to 6.

Assign cookies: match smallest with smallest

In Assign Cookies a child is content with a cookie at least their greed factor. Sort both lists and give each cookie, smallest first, to the least greedy child still waiting if it is big enough. The exchange argument: if an optimal assignment gives that child a bigger cookie than needed, swap it with the smallest that would do — whoever held that one is still content. Sorting first is what makes it a two-pointer sweep; see sorting algorithms.

When greedy fails

Greedy has no safety net, so know the classic failures. Coin change: largest-first is optimal for coin systems like the rupee's, but not for arbitrary coins — Coin Change needs dynamic programming.

1. With coins 1, 2, 5, 10, 20, 50, largest-first makes 80 from 50 + 20 + 10, and nothing does it in fewer than 3. Systems like this, where greedy is always optimal, are called canonical — which is why it feels natural at a till.
2. With coins 1, 3, 4, largest-first takes the 4 and is left with 1 + 1: 3 coins. But 3 + 3 needs only 2. Taking the 4 looked best and was not, and greedy never reconsiders; dynamic programming does.

Fractional versus 0/1 knapsack: when you may take part of an item, best value per kilogram first is optimal; when items are whole, the same rule loses, because the exchange argument needs to swap part of an item. That is the knapsack problem.

A greedy rule that sounds right is a hypothesis. Look for a counterexample with three or four items before you code it.

More greedy shapes

• Lemonade Change: for a $20, give $10 + $5 rather than three $5s, keeping the most flexible bills.
• Maximum Units on a Truck: most units per box first.
• Gas Station: if the tank goes negative between stations i and j, no station in between can be the start.
• Partition Labels: extend each piece to the last occurrence of every letter in it.
• Minimum Number of Platforms: sort arrivals and departures separately and sweep them.
• Candy: two greedy passes, one per direction.

Time and space complexity

Most greedy solutions cost what their sort costs, because the rule needs the input in some order; the sweep afterwards is linear.

How to recognise a greedy problem

• A maximum or minimum count — the most meetings, the fewest jumps, the most children — where choices do not interact much beyond an obvious order.
• A natural order to process things in: by end time, size, deadline or ratio.
• A rule you can phrase as "always take the … that leaves the most room".
• A small counterexample is hard to find. (If you find one easily, think dynamic programming.)
• Large constraints (n up to 10⁵) and a single number as the answer.

Common mistakes

• Trusting a rule without a proof or a test: earliest start and largest coin first both sound right.
• Sorting by the wrong key: activity selection sorts by end; merging intervals by start.
• Touching endpoints: does a meeting ending at 4 clash with one starting at 4? Match >= or > to the statement.
• Being greedy on the wrong quantity: the longest single jump, not the level's farthest reach.
• Forgetting the impossible case: a zero you cannot pass, less fuel than cost.

Practice in this order

1. Assign Cookies: sort both, match smallest with smallest.
2. Lemonade Change: keep the most useful bills.
3. Maximum Units on a Truck: best ratio first.
4. Jump Game: keep only the farthest reach.
5. Jump Game II: count levels, the second program.
6. Non-overlapping Intervals: activity selection, counted the other way.
7. Gas Station: a one-pass greedy with a proof you must find.
8. Partition Labels: extend to the farthest last occurrence.
9. Candy: two passes that together satisfy both neighbours.

The greedy problem list has every greedy problem in the catalogue. Next on the road is intervals, where sorting and greedy sweeps meet.