Greedy Algorithms

CS F364 — Design & Analysis of Algorithms | Summer 2026

Interval scheduling, interval stabbing, cookie assignment, knapsack

← Practice

NoteProblem 1

Oxen pairing. We have n oxen, each with strength S_i. We need to pair them into teams of exactly two to pull a plow; a team of oxen i and j can pull the plow only if S_i + S_j \ge P, where P is the plow’s weight. Each ox can be in at most one team. Maximize the number of teams formed.

Algorithm (strongest-weakest pairing):

  1. Sort the strengths in ascending order.
  2. Maintain two pointers: i = 1 (weakest), j = n (strongest).
  3. While i < j:
    • If S_i + S_j \ge P, form a team, increment i, decrement j.
    • Otherwise, the weakest ox cannot pair with anyone (since the strongest partner is insufficient); skip it by incrementing i.

Proof of optimality (exchange argument): In any optimal solution, if the weakest ox is paired, it must be with some ox. Replacing that partner with the strongest unpaired ox (which can only be stronger) cannot reduce the number of feasible teams. If the weakest cannot pair even with the strongest, it will never be pairable and can be safely discarded.

Time: O(n\log n) for sorting, O(n) for the two-pointer scan.

NoteProblem 2

Spectrum monitoring. You want to monitor every frequency in the electromagnetic spectrum between L and H. You have n technologies T_1,\dots,T_n, each with an interval [l_i, h_i] of frequencies it can monitor. Pick as few technologies as possible that together cover [L,H].

Algorithm (earliest-start-first greedy):

  1. Filter all technologies with l_i \le L (those that can cover the start).
  2. Among them, select the one with the maximum h_i, say T_{\max}.
  3. Set L = h_{\max} and repeat until L \ge H.
  4. If at any step no technology covers L, covering is impossible.

Proof of optimality (exchange argument): At each step, picking the technology that extends coverage farthest to the right is optimal. Any alternative choice that covers L has end \le h_{\max}, so it cannot cover more of the remaining interval. By induction, the greedy choice leads to a minimum-cardinality cover.

Time: O(n\log n) after sorting by start point.

NoteProblem 3

Cookie assignment. You are baby-sitting n children and have m > n cookies. Each child must get exactly one cookie. Child i has a greed factor g_i (the minimum cookie size they will be content with); cookie j has size s_j. Maximize the number of content children (those assigned a cookie with g_i \le s_j). Give a greedy algorithm, prove it optimal, and give an efficient implementation.

Algorithm:

  1. Sort cookies by size ascending.
  2. Sort children by greed factor ascending.
  3. For each child (in increasing order of greed):
    • Assign the smallest cookie that satisfies s_j \ge g_i.
    • If no such cookie remains, leave the child discontent.

Proof of optimality (exchange argument): Consider an optimal assignment. Let g_1 \le g_2 \le \dots \le g_n be the sorted children. For the least greedy child g_1, if the optimal solution gives a larger cookie than necessary, swapping it with the smallest feasible cookie (which our algorithm would assign) frees up a larger cookie for a greedier child without reducing the number of content children. By induction, the greedy choice is optimal at each step.

Implementation:

sort(s), sort(g)
j = 1
count = 0
for i = 1 to n:
    while j <= m and s[j] < g[i]:
        j++
    if j <= m:
        count++, j++
return count

Time: O(n\log n + m\log m) for sorting, O(m) for the scan.

NoteProblem 4

Interval stabbing. Given n > 1 intervals with start array S[1..n] and end array E[1..n], find a set of points X of minimum size such that every interval contains at least one point in X. Design the algorithm and prove optimality.

Algorithm (earliest-end-first greedy):

  1. Sort intervals by end point E[i].
  2. Let X = \emptyset.
  3. For each interval (S[i], E[i]) in sorted order:
    • If no point in X lies within (S[i], E[i]), add E[i] to X.

Proof of optimality (exchange argument): Let G be the greedy solution and OPT an optimal solution. Sort both by their chosen points. Let i be the first index where G[i] \neq OPT[i]. The greedy algorithm picks the earliest-ending interval’s end point. Any optimal solution must stab this interval with some point \le G[i]. Replacing OPT[i] with G[i] cannot increase the number of points needed, as G[i] stabs all intervals that OPT[i] stabs (and possibly more, since G[i] is the earliest possible rightmost point). By induction, |G| \le |OPT|.

Time: O(n\log n) for sorting, O(n) for the scan.

NoteProblem 5

Max-cardinality knapsack. You have n items with weights w_1,\dots,w_n and a bag of capacity W. Select as many items as possible whose total weight \le W. Describe a simple efficient algorithm and prove it gives the optimal output.

Algorithm (Container Loading):

  1. Sort items by weight in ascending order.
  2. Greedily pick the lightest items until the next item would exceed W.

Proof of optimality (exchange argument): Let G = \{g_1, g_2, \dots, g_k\} be the greedy solution (items in sorted order). Let OPT = \{o_1, o_2, \dots, o_k\} be an optimal solution with items sorted. If G and OPT differ, let i be the first position where g_i \neq o_i. By construction g_i \le o_i (greedy always picks the smallest remaining feasible item). Replacing o_i with g_i in OPT yields a solution with \le the same total weight and the same cardinality. By induction, the greedy solution has maximum cardinality.

Note that this is the classic “Container Loading” problem, not the 0-1 knapsack (which maximizes value). When maximizing count with uniform value, the lightest-first strategy is optimal.

Time: O(n\log n) for sorting, O(n) for the scan.