The Greedy Paradigm & Greedy vs DP

Greedy algorithms construct optimal solutions through a sequence of irrevocable local choices, bypassing exhaustive search and subproblem tabulation. Guided by the Greedy-Choice Property and validated through formal exchange arguments, greedy strategies deliver high-speed $O(n\log n)$ solutions for interval scheduling, minimum spanning trees, and fractional resource allocation.

The Greedy Paradigm builds candidate solutions incrementally by selecting the locally optimal choice at each step without backtracking or exploring alternative branches. Pioneered formally through Jack Edmonds' matroid theory (1971), greedy correctness requires establishing two mathematical conditions: the Greedy-Choice Property and Optimal Substructure.

By the end of this chapter, you will be able to:

1. Formulate the Greedy-Choice Property and Optimal Substructure with mathematical rigor.
2. Execute the Exchange Argument to prove by induction that a greedy sequence matches or exceeds any hypothetical optimal solution.
3. Implement and trace Interval Scheduling (Activity Selection) and Fractional Knapsack algorithms in $O(n\log n)$ time.
4. Identify greedy failure modes through counterexamples (non-canonical coin systems, 0/1 Knapsack) that mandate Dynamic Programming.
5. Evaluate trade-offs between greedy heuristics ($O(n\log n)$ speed, $O(1)$ memory) and dynamic programming ($O(n\cdot W)$ optimality guarantees).

A Greedy Algorithm constructs a candidate solution incrementally through a sequence of locally optimal choices without reconsidering earlier choices or evaluating downstream branches:

• Irrevocability: Once a choice is made, it is permanent. The algorithm never backtracks to reconsider alternatives.
• Top-Down Reduction: Subproblem reduction occurs immediately after each greedy choice is made.

The standard rigorous method for proving greedy correctness is the Exchange Argument: we establish that any hypothetical optimal solution can be transformed into the greedy solution step-by-step without degrading objective value.

Given $n$ intervals with start times $S[i]$ and finish times $F[i]$, selecting activities in ascending order of finish time $F[i]$ produces a schedule of maximum possible cardinality.

Inductive Proof via Exchange:

Let $G=\{g_1,g_2,\dots ,g_k\}$ be the set of activities selected by the greedy algorithm, ordered by finish time: $F[g_1]\le F[g_2]\le \cdots \le F[g_k]$.
Let $O=\{o_1,o_2,\dots ,o_m\}$ be an arbitrary optimal solution, ordered by finish time: $F[o_1]\le F[o_2]\le \cdots \le F[o_m]$. We must prove $k=m$.

1. Base Case ($r=1$): By construction, greedy selects $g_1$ such that $F[g_1]={\min }_{i}F[i]$.
   Therefore, $F[g_1]\le F[o_1]$.
   Construct modified solution $O^{\prime }=(O\setminus \{o_1\})\cup \{g_1\}$. Since $F[g_1]\le F[o_1]\le S[o_2]$, activity $g_1$ does not conflict with $o_2$. Thus $O^{\prime }$ is valid and $|O^{\prime }|=|O|=m$.
2. Inductive Step: Assume there exists an optimal solution whose first $r$ activities match $G$: $\{g_1,g_2,\dots ,g_r,o_{r+1},\dots ,o_m\}$.
   Because greedy selects $g_{r+1}$ as the activity with earliest finish time starting after $F[g_r]$, we have $F[g_{r+1}]\le F[o_{r+1}]$.
   Substituting $g_{r+1}$ in place of $o_{r+1}$ leaves activities $o_{r+2},\dots ,o_m$ valid because $F[g_{r+1}]\le F[o_{r+1}]\le S[o_{r+2}]$.
3. Conclusion: By induction, the entire set $G$ can replace the first $k$ elements of an optimal solution. If $m>k$, there would exist an activity $o_{k+1}$ compatible with $g_k$, contradicting greedy termination. Hence, $k=m$, and $G$ is globally optimal. $■$

Consider $n=8$ activities sorted by ascending finish times:

• $A_1:[1,4]$, $A_2:[3,5]$, $A_3:[0,6]$, $A_4:[5,7]$, $A_5:[3,9]$, $A_6:[5,9]$, $A_7:[6,10]$, $A_8:[8,11]$

Result: Maximum compatible set cardinality is $3$: $\{A_1,A_4,A_8\}$. Runtime: $\Theta (n\log n)$ for initial sorting.

export interface Interval {
  id: number;
  start: number;
  finish: number;
}

export function selectActivities(activities: Interval[]): Interval[] {
  // Sort by ascending finish times - O(n log n)
  const sorted = [...activities].sort((a, b) => a.finish - b.finish);
  const selected: Interval[] = [];
  let lastFinish = -Infinity;

  for (const act of sorted) {
    if (act.start >= lastFinish) {
      selected.push(act);
      lastFinish = act.finish;
    }
  }

  return selected;
}

Given knapsack capacity $W=50\text{ kg}$ and 4 items:

• Item 1: v_1 = 60, w_1 = 10 \implies \rho_1 = 6.0\text{ </span>/kg}$
• Item 2: v_2 = 100, w_2 = 20 \implies \rho_2 = 5.0\text{ </span>/kg}$
• Item 3: v_3 = 120, w_3 = 30 \implies \rho_3 = 4.0\text{ </span>/kg}$
• Item 4: v_4 = 50, w_4 = 25 \implies \rho_4 = 2.0\text{ </span>/kg}$

Conclusion: Greedily sorting by value density yields maximum possible profit of </span>240$in$O(n \log n)$ time.

Whenever the Greedy-Choice Property fails, greedy algorithms yield suboptimal or incorrect results.

Given coin denominations $C$ and target value $V$:

Matroid Theory Insight (Pearson, 1994): A coin system is canonical if and only if the change-making problem satisfies Pearson's $O(n^3)$ algebraic test. Arbitrary coin systems lack the greedy-choice property and require $O(n\cdot V)$ Dynamic Programming.

1. Applying Greedy to 0/1 Knapsack:
   • Greedily sorting by value density works for fractional knapsack, but fails catastrophically for 0/1 knapsack where items cannot be divided. 0/1 knapsack requires pseudo-polynomial DP.
2. Sorting by Start Time in Interval Scheduling:
   • Selecting activities by earliest start time fails (e.g., an activity starting at $0$ spanning until $100$ would block multiple shorter activities). Always sort by earliest finish time.
3. Floating-Point Density Inaccuracy:
   • In fractional knapsack, comparing density using division v1 / w1 < v2 / w2 induces IEEE-754 precision errors. Compare using cross-multiplication: v1 * w2 < v2 * w1.

• Huffman Coding (Data Compression): Greedily merges the two least frequent character trees to construct optimal prefix codes (gzip, JPEG).
• Network Routing Protocols (OSPF / Prim's MST): Dijkstra and Prim greedily extend shortest routes and minimum spanning connections.
• CPU Task Schedulers (Earliest Deadline First / EDF): Schedules real-time processes greedily by closest deadline to guarantee optimal schedulability on uniprocessors.

1. Non-overlapping Intervals (LeetCode 435) — Activity selection greedy finish-time ordering.
2. Jump Game (LeetCode 55) — Greedy reachability tracking in $O(n)$ time.
3. Gas Station (LeetCode 134) — Greedy circular tour validation in single pass.

1. Edmonds, J. (1971). Matroids and the greedy algorithm. Mathematical Programming, 1(1), 127–136.
2. Pearson, D. (1994). A polynomial-time algorithm for the change-making problem. Operations Research Letters, 33(3), 231–234.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 15 (Greedy Algorithms). MIT Press.
4. Kleinberg, J., & Tardos, É. (2006). Algorithm Design, Chapter 4 (Greedy Algorithms). Pearson.