Greedy Algorithms
debt(d9/e7/b5/t7)
Closest to 'silent in production until users hit it' (d9). The detection_hints field explicitly states 'automated: no' and describes the pattern as a scheduling/resource allocation problem solved suboptimally. There is no static analysis tool that can detect when a greedy algorithm has been incorrectly applied to a problem that requires DP or backtracking — the code runs without errors, produces plausible-looking (but wrong) output, and the bug only surfaces when edge-case inputs expose the suboptimality, often in production or under specific data distributions.
Closest to 'cross-cutting refactor across the codebase' (e7). The quick_fix states the fix requires verifying the greedy choice property and switching to dynamic programming when subproblems overlap. Replacing a greedy solution with DP is not a one-line patch — it requires redesigning the algorithm, introducing memoization or tabulation structures, and often rethinking data flow. If the greedy approach was used as a shared utility or embedded in multiple scheduling/allocation components, the rework crosses multiple files and logic boundaries, placing it at e7.
Closest to 'persistent productivity tax' (b5). The applies_to covers both web and cli contexts broadly. A greedy algorithm embedded in a core optimisation routine imposes ongoing burden: future maintainers must understand why the approach was chosen, whether it's correct for new input shapes, and face the risk of silent regressions when problem constraints change. It's not system-defining (b9) but does slow down multiple work streams when the algorithm is load-bearing in scheduling or resource allocation logic.
Closest to 'serious trap — contradicts how a similar concept works elsewhere' (t7). The misconception field explicitly states the canonical wrong belief: 'Greedy algorithms always find the optimal solution.' This is a well-documented but serious trap — competent developers familiar with dynamic programming often assume greedy is a valid shortcut for problems like the general knapsack or arbitrary-denomination coin change, where it silently produces wrong answers. The trap is compounded by the fact that greedy IS correct for superficially similar problems (e.g. standard coin systems, activity selection), making the boundary non-obvious and the wrong assumption highly plausible.
Also Known As
TL;DR
Explanation
A greedy algorithm selects the best available option at each step without reconsidering previous choices. It works when: the greedy choice is safe (local optimum leads to global optimum) and the problem has optimal substructure. Classic examples: coin change (if denominations allow), interval scheduling (sort by end time), Huffman coding, Kruskal/Prim for minimum spanning trees. Fails for: general coin change (e.g. coins {1,3,4} — greedy for 6 gives {4,1,1} not optimal {3,3}).
Diagram
flowchart TD
PROBLEM[Optimisation problem] --> CHOICE[Make locally optimal choice<br/>at each step]
CHOICE --> IRREV[Never reconsider<br/>irrevocable decision]
IRREV --> NEXT[Move to next subproblem]
NEXT -->|done?| SOLUTION[Global solution]
subgraph Works For
COIN[Coin change - large denominations first]
HUFFMAN[Huffman coding]
DIJKSTRA[Dijkstra shortest path]
PRIM[Prim minimum spanning tree]
end
subgraph Does NOT Work For
KNAPSACK[0-1 Knapsack - needs DP]
TSP[Travelling Salesman]
end
style SOLUTION fill:#238636,color:#fff
style KNAPSACK fill:#f85149,color:#fff
style TSP fill:#f85149,color:#fff
Common Misconception
Why It Matters
Common Mistakes
- Applying greedy to problems where it doesn't hold — coin change with arbitrary denominations requires DP.
- Not sorting before applying greedy — most greedy algorithms require the input in a specific order.
- Confusing greedy with DP — if a problem has overlapping subproblems, DP is required; if choices are independent, greedy may work.
- Not proving the greedy choice property — assuming greedy works without verifying leads to subtly wrong solutions.
Code Examples
// Greedy coin change fails for non-standard denominations:
function greedyChange(int $amount, array $coins): array {
rsort($coins); // Sort descending
$result = [];
foreach ($coins as $coin) {
while ($amount >= $coin) { $result[] = $coin; $amount -= $coin; }
}
return $result;
}
// greedyChange(6, [1,3,4]) returns [4,1,1] — 3 coins
// Optimal: [3,3] — 2 coins. Greedy fails here.// DP coin change — always optimal:
function dpChange(int $amount, array $coins): int {
$dp = array_fill(0, $amount + 1, PHP_INT_MAX);
$dp[0] = 0;
for ($i = 1; $i <= $amount; $i++) {
foreach ($coins as $coin) {
if ($coin <= $i && $dp[$i - $coin] !== PHP_INT_MAX) {
$dp[$i] = min($dp[$i], $dp[$i - $coin] + 1);
}
}
}
return $dp[$amount] === PHP_INT_MAX ? -1 : $dp[$amount];
}