Greedy Algorithms: Local Optimality, Proofs, and Decision Frameworks

A Greedy Algorithm constructs a solution incrementally, making the locally optimal choice at each stage with the goal of discovering the global optimum. Unlike Dynamic Programming, greedy algorithms never reconsider or backtrack on previously made decisions.

⚡ Quick Dive

The Greedy Criteria Checklist

A greedy strategy is guaranteed to yield a globally optimal solution if and only if the problem exhibits:

  1. Greedy Choice Property: A globally optimal solution can be reached by making locally optimal (greedy) choices without looking ahead or backtracking.
  2. Optimal Substructure: An optimal solution to the overall problem contains optimal solutions to its subproblems.

Classic Greedy Algorithms Reference

Problem Greedy Heuristic Time Complexity Optimality Guarantee
Activity Selection (Intervals) Pick activity with earliest end time $O(n \log n)$ (Sort) ✅ Globally Optimal
Fractional Knapsack Pick item with highest value-to-weight ratio $O(n \log n)$ ✅ Globally Optimal
Huffman Coding Merge two trees with lowest frequency counts $O(n \log n)$ ✅ Globally Optimal (Optimal Prefix Code)
Dijkstra's Algorithm Expand node with minimum known distance $O((V+E) \log V)$ ✅ Optimal (Non-negative weights)
Kruskal's / Prim's MST Add edge with minimum weight that prevents cycles $O(E \log V)$ ✅ Globally Optimal
Coin Change (Canonical) Pick largest coin denomination $\le$ remaining amount $O(n)$ ⚠️ Only for canonical currency systems

📖 Extended Guide

1. Activity Selection / Interval Scheduling

Problem: Given $N$ activities with start time $s_i$ and finish time $f_i$, find the maximum number of mutually compatible activities.

Greedy Rule:

Always select the activity that finishes earliest ($f_i$ is minimized). This leaves maximum remaining time for subsequent activities.

package main

import (
	"fmt"
	"sort"
)

type Interval struct {
	start, end int
}

func MaxNonOverlappingIntervals(intervals []Interval) int {
	if len(intervals) == 0 {
		return 0
	}

	// Sort intervals by earliest finish time
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i].end < intervals[j].end
	})

	count := 1
	lastEnd := intervals[0].end

	for i := 1; i < len(intervals); i++ {
		if intervals[i].start >= lastEnd {
			count++
			lastEnd = intervals[i].end
		}
	}

	return count
}

func main() {
	tasks := []Interval{{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}}
	fmt.Printf("Max Scheduled Tasks: %d\n", MaxNonOverlappingIntervals(tasks)) // 4
}

2. Huffman Lossless Data Compression

Huffman coding builds variable-length prefix codes based on character frequencies. Frequently occurring characters receive shorter bit sequences.

Frequencies: A: 45%, B: 13%, C: 12%, D: 16%, E: 9%, F: 5%

Huffman Tree Construction:
1. Place all nodes in Min-Priority Queue by frequency.
2. Repeatedly extract two lowest frequency nodes, create parent with combined frequency, and reinsert.
3. Assign '0' to left branches and '1' to right branches.

No code is a prefix of another code (Prefix-Free Code), enabling unambiguous streaming decompression without delimiters.

3. When Greedy Fails: Greedy vs. Dynamic Programming

Example: Coin Change for Amount = 6 with Coins {1, 3, 4}

Greedy Strategy (Largest coin first):
- Pick 4 -> Remaining: 2 -> Pick 1 -> Pick 1
- Coins used: {4, 1, 1} (Total: 3 coins)

Optimal DP Strategy:
- Coins used: {3, 3} (Total: 2 coins!)
- Greedy fails because picking '4' traps the algorithm in a suboptimal branch.

Decision Matrix:

  • If a locally optimal choice never restricts or invalidates future optimal choices $\to$ Greedy.
  • If choices interact with future constraints and require evaluating combinations $\to$ Dynamic Programming.
⌂ All Guides