34  Algorithm Design — Greedy Algorithms

35 Algorithm Design — Greedy Algorithms

Week 6, Session 2. CSS 343.

35.1 Warmup

Assign Cookies (#455). Children have greed factors g[i]; cookies have sizes s[j]. Each child is satisfied if some cookie ≥ their greed. Maximize satisfied children.

class Solution {
 public:
  int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int i = 0, j = 0;
    while (i < (int)g.size() && j < (int)s.size()) {
      if (s[j] >= g[i]) ++i;
      ++j;
    }
    return i;
  }
};

Sort both. Walk a two-pointer scan. Greedy: give the smallest cookie that satisfies the smallest unhappy child. O(n log n) from the sort.

35.2 Learning objectives

  1. Formulate the greedy choice for a given optimization problem.
  2. Apply activity selection and argue correctness via exchange argument.
  3. Distinguish problems where greedy is optimal from those where it fails.
  4. Recognize Huffman coding and Dijkstra’s algorithm as greedy instances.
  5. Solve Jump Game using a greedy reachability scan in O(n).

35.3 The paradigm

At each step, make the locally optimal choice and commit to it. No backtracking, no enumeration of alternatives.

Two properties make greedy work:

  1. Greedy choice property: a globally optimal solution can be reached by making locally optimal choices.
  2. Optimal substructure: an optimal solution contains optimal solutions to subproblems.

When both hold, greedy is optimal. When only the second holds, you need DP.

35.4 Activity selection

Given n activities each with a start and finish time. Pick the maximum number of non-overlapping activities.

Greedy choice: pick the activity that finishes earliest. Then recurse on activities starting after that finish time.

int maxActivities(vector<pair<int,int>>& acts) {  // (start, finish)
  sort(acts.begin(), acts.end(),
       [](const auto& a, const auto& b) { return a.second < b.second; });
  int count = 0;
  int lastFinish = INT_MIN;
  for (const auto& [s, f] : acts) {
    if (s >= lastFinish) {
      ++count;
      lastFinish = f;
    }
  }
  return count;
}

35.4.1 Why greedy works here

Exchange argument: suppose an optimal solution does not include the earliest-finishing activity. Swap the first activity of the optimal with the earliest-finishing one. The swap is legal (it finishes earlier, so it does not conflict with any subsequent choice in the optimal). The swapped solution has the same count. Therefore there exists an optimal that includes the greedy choice. ∎

35.5 Fractional knapsack — greedy is optimal

Items have value v_i and weight w_i. You can take fractions. Maximize total value within capacity W.

Greedy choice: sort by value-per-weight ratio descending. Take items in order, fractioning the last one as needed.

double fractionalKnapsack(vector<pair<double, double>>& items, double W) {
  // sort by value/weight descending
  sort(items.begin(), items.end(),
       [](const auto& a, const auto& b) {
         return a.first / a.second > b.first / b.second;
       });
  double value = 0;
  for (const auto& [v, w] : items) {
    if (W <= 0) break;
    if (w <= W) { value += v; W -= w; }
    else { value += v * (W / w); W = 0; }
  }
  return value;
}

35.6 0/1 Knapsack — greedy fails

Same problem but you cannot take fractions. Items must be taken whole or not at all.

Consider items {(60, 10), (100, 20), (120, 30)}, capacity 50.

Ratios: 6, 5, 4. Greedy takes item 1 (60, weight 10) then item 2 (100, weight 20) = 160 value, weight 30, remaining capacity 20. Cannot take item 3. Result: 160.

But optimal: item 2 + item 3 = 220 value, weight 50. Greedy is suboptimal by 60.

For 0/1 knapsack we need DP — coming in Chapter 33.

35.7 Coin change — greedy fails sometimes

For coin denominations like US coins (1, 5, 10, 25), greedy works: always pick the largest coin ≤ remaining.

For denominations {1, 3, 4}, target 6: greedy gives 4 + 1 + 1 = 3 coins. Optimal: 3 + 3 = 2 coins. Greedy is wrong.

Greedy is the most rewarding algorithm to recognize and the most dangerous to apply without proof. When in doubt, fall back to DP — DP includes greedy as a special case.

35.8 Huffman as greedy

Recall Huffman coding from Chapter 24. At each step we combine the two least-frequent nodes. Greedy choice. Provably optimal — proof is in CLRS.

35.9 Dijkstra as greedy

Each iteration settles the vertex with the smallest tentative distance. Greedy choice. Optimal for non-negative weights. With negative weights, the greedy choice property breaks.

35.10 Jump Game

Jump Game (#55). Given nums where nums[i] is the maximum jump from position i, can you reach the end?

class Solution {
 public:
  bool canJump(vector<int>& nums) {
    int maxReach = 0;
    for (int i = 0; i < (int)nums.size(); ++i) {
      if (i > maxReach) return false;
      maxReach = max(maxReach, i + nums[i]);
    }
    return true;
  }
};

Greedy: maintain the farthest reachable index. Single pass. O(n).

35.11 Try it

Solve Jump Game II (#45) — minimum number of jumps to reach the end. The greedy version uses two pointers: current end, farthest reachable. When you hit current end, increment jump count and move it to farthest.

35.12 Self-check

1. Greedy is provably optimal for:
b. Exchange argument proves optimality. The others either need DP or have no known polynomial-time optimal algorithm.
2. Why does greedy fail for 0/1 knapsack but work for fractional knapsack?
c. With fractions, the greedy choice always exhausts capacity efficiently. With whole items, you can end up with unfillable gaps.

35.13 Challenges

  1. Jump Game II (#45).
  2. Gas Station (#134).
  3. Best Time to Buy and Sell Stock II (#122).
  4. Task Scheduler (#621) — greedy with priority queue.

35.14 Where this fits

Greedy works when it works. When it fails, DP is the next paradigm — and DP often dominates greedy with only a polynomial blow-up.

You are here Coming up
Greedy paradigm, exchange argument, when greedy fails Chapter 33: dynamic programming I