Greedy Fundamentals

TL;DR

Greedy algorithms make locally optimal choices hoping to find global optimum. Greedy applies when problem has greedy choice property: globally optimal solution can be built from locally optimal choices without backtracking, and optimal substructure: optimal solution contains optimal solutions to subproblems. Prove greedy correctness using exchange argument: show any optimal solution that differs from greedy choice can be improved by swapping elements, leading to greedy solution. Activity selection exemplifies greedy: sort activities by finish time, greedily select activities that don't conflict. Common pattern: sort/prioritize input, then greedily select based on criteria. Greedy fails when problem lacks one property (e.g., coin change with arbitrary denominations). Always verify both properties before applying greedy.

Core Concepts

Greedy Choice Property

Greedy choice property means a globally optimal solution can be reached by making locally optimal (greedy) choices.

Key Distinction:

• Local optimum: Best choice available at current step
• Global optimum: Best overall solution considering entire problem
• Connection: For greedy to work, locally optimal choices must lead to global optimum

Why It Matters: Without this property, greedy can miss better solutions by committing to local choices.

Example - Activity Selection: Choosing activity finishing earliest (local optimum) leaves most room for remaining activities (global optimum).

Optimal Substructure

Optimal substructure means optimal solution contains optimal solutions to subproblems.

Formal Definition: If problem P has optimal substructure, then optimal solution to P uses optimal solutions to subproblems P₁, P₂, ..., Pₖ.

How to Verify:

1. Assume optimal solution to problem exists
2. Show that solution uses optimal solutions to subproblems
3. Contradiction shows if not optimal substructure

Importance: Allows building solution incrementally—each step guaranteed to maintain optimality.

The Exchange Argument

Exchange argument proves greedy correctness by showing any alternative solution can be improved by exchanging elements toward the greedy solution.

Structure:

1. Assume optimal solution O differs from greedy solution G
2. Find first position where O and G differ
3. Show swapping O's choice with G's choice doesn't decrease optimality
4. Repeat until O becomes G, proving G is optimal

Power: Constructive proof showing greedy solution is at least as good as any other solution.

When Greedy Fails

Lack of greedy choice property: Problem requires considering combinations of choices (e.g., coin change with arbitrary denominations).

Lack of optimal substructure: Optimal solution doesn't contain optimal solutions to subproblems (e.g., longest simple path in graph).

Interdependencies: Choices affect later constraints in non-local ways.

Key Concepts

Problem Classification

Greedy Applicable:

• Interval scheduling problems
• Activity selection problems
• Graph problems with natural ordering (MST, shortest path with non-negative weights)

Greedy Fails:

• General knapsack (0/1 variant)
• Arbitrary coin change (DP required)
• Graph problems with negative weights

Proof Techniques

Exchange Argument: Most common, shows greedy solution as good as any other.

Induction: Prove by mathematical induction that greedy maintains optimality at each step.

Cut and Paste: Remove greedy choice from optimal solution and paste into new solution, showing no loss in optimality.

Common Greedy Patterns

1. Sort then select: Order elements, greedily select based on criteria
2. Priority-based selection: Use priority queue to always select best available option
3. Interval problems: Sort by relevant endpoint, greedily select non-overlapping intervals
4. Resource allocation: Allocate resources to maximize return

Key Algorithms

Activity Selection Pattern

Problem: Select maximum number of non-overlapping activities.

Greedy Choice: Among remaining activities, select one finishing earliest.

Why It Works: Selecting earliest-finishing activity leaves maximum time for remaining activities.

Proof: Exchange argument shows earliest-finishing is in some optimal solution; repeating greedy choice maintains optimality.

General Greedy Framework

1. Sort/prepare input by relevant criteria
2. Initialize result container
3. For each element in sorted order:
   - If element satisfies greedy criteria:
     - Add to result
4. Return result

Practical Example

Python

# Activity Selection Problem
def activity_selection(activities):
    """
    activities: list of (start_time, end_time, activity_name)
    Returns list of selected non-overlapping activities
    """
    # Sort by end time (greedy criterion)
    sorted_activities = sorted(activities, key=lambda x: x[1])

    selected = [sorted_activities[0]]
    last_end = sorted_activities[0][1]

    for start, end, name in sorted_activities[1:]:
        # Select if doesn't overlap with last selected activity
        if start >= last_end:
            selected.append((start, end, name))
            last_end = end

    return selected

# Interval covering (variation)
def minimum_intervals_to_cover(intervals, target_start, target_end):
    """
    intervals: list of (start, end)
    Returns minimum number of intervals to cover [target_start, target_end]
    """
    # Sort by start time
    intervals = sorted(intervals)

    selected = []
    current_pos = target_start
    i = 0
    n = len(intervals)

    while current_pos < target_end:
        # Find interval covering current_pos with furthest reach
        farthest = current_pos

        while i < n and intervals[i][0] <= current_pos:
            farthest = max(farthest, intervals[i][1])
            i += 1

        if farthest == current_pos:
            return None  # Cannot cover target range

        selected.append((current_pos, farthest))
        current_pos = farthest

    return selected

# Greedy value maximization
def maximize_value_with_weight_limit(items, weight_limit):
    """
    items: list of (weight, value, name)
    Returns maximum value and selected items
    """
    # Sort by value/weight ratio (greedy criterion)
    sorted_items = sorted(items, key=lambda x: x[1]/x[0], reverse=True)

    total_weight = 0
    total_value = 0
    selected = []

    for weight, value, name in sorted_items:
        if total_weight + weight <= weight_limit:
            selected.append(name)
            total_weight += weight
            total_value += value

    return total_value, selected

# Tests
activities = [(1, 3, 'A'), (2, 5, 'B'), (4, 6, 'C'), (6, 9, 'D'), (5, 7, 'E')]
print(activity_selection(activities))

intervals = [(1, 3), (2, 5), (3, 7), (5, 9), (8, 10)]
print(minimum_intervals_to_cover(intervals, 1, 10))

items = [(2, 10, 'item1'), (3, 20, 'item2'), (5, 30, 'item3')]
print(maximize_value_with_weight_limit(items, 7))

Java

import java.util.*;

public class GreedyFundamentals {

    // Activity Selection
    static class Activity implements Comparable<Activity> {
        int start, end;
        String name;

        Activity(int start, int end, String name) {
            this.start = start;
            this.end = end;
            this.name = name;
        }

        @Override
        public int compareTo(Activity other) {
            return Integer.compare(this.end, other.end);
        }
    }

    public static List<Activity> activitySelection(Activity[] activities) {
        Arrays.sort(activities);
        List<Activity> selected = new ArrayList<>();
        selected.add(activities[0]);
        int lastEnd = activities[0].end;

        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= lastEnd) {
                selected.add(activities[i]);
                lastEnd = activities[i].end;
            }
        }

        return selected;
    }

    // Interval Covering
    static class Interval implements Comparable<Interval> {
        int start, end;

        Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Interval other) {
            return Integer.compare(this.start, other.start);
        }
    }

    public static List<Interval> minimumIntervalsCover(
            Interval[] intervals, int targetStart, int targetEnd) {
        Arrays.sort(intervals);
        List<Interval> selected = new ArrayList<>();

        int currentPos = targetStart;
        int i = 0;

        while (currentPos < targetEnd) {
            int farthest = currentPos;

            while (i < intervals.length && intervals[i].start <= currentPos) {
                farthest = Math.max(farthest, intervals[i].end);
                i++;
            }

            if (farthest == currentPos) return null;

            selected.add(new Interval(currentPos, farthest));
            currentPos = farthest;
        }

        return selected;
    }

    // Greedy Value Maximization
    static class Item implements Comparable<Item> {
        double weight, value;
        String name;

        Item(double weight, double value, String name) {
            this.weight = weight;
            this.value = value;
            this.name = name;
        }

        @Override
        public int compareTo(Item other) {
            return Double.compare(other.value / other.weight,
                                 this.value / this.weight);
        }
    }

    public static Object[] maximizeValue(Item[] items, double weightLimit) {
        Arrays.sort(items);
        double totalValue = 0;
        double totalWeight = 0;
        List<String> selected = new ArrayList<>();

        for (Item item : items) {
            if (totalWeight + item.weight <= weightLimit) {
                selected.add(item.name);
                totalWeight += item.weight;
                totalValue += item.value;
            }
        }

        return new Object[]{totalValue, selected};
    }

    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 3, "A"),
            new Activity(2, 5, "B"),
            new Activity(4, 6, "C"),
            new Activity(6, 9, "D"),
            new Activity(5, 7, "E")
        };
        System.out.println(activitySelection(activities));

        Interval[] intervals = {
            new Interval(1, 3),
            new Interval(2, 5),
            new Interval(3, 7),
            new Interval(5, 9),
            new Interval(8, 10)
        };
        System.out.println(minimumIntervalsCover(intervals, 1, 10));

        Item[] items = {
            new Item(2, 10, "item1"),
            new Item(3, 20, "item2"),
            new Item(5, 30, "item3")
        };
        Object[] result = maximizeValue(items, 7);
        System.out.println("Value: " + result[0] + ", Items: " + result[1]);
    }
}

TypeScript

// Activity Selection
interface Activity {
    start: number;
    end: number;
    name: string;
}

function activitySelection(activities: Activity[]): Activity[] {
    // Sort by end time
    const sorted = activities.sort((a, b) => a.end - b.end);

    const selected: Activity[] = [sorted[0]];
    let lastEnd = sorted[0].end;

    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i].start >= lastEnd) {
            selected.push(sorted[i]);
            lastEnd = sorted[i].end;
        }
    }

    return selected;
}

// Interval Covering
interface Interval {
    start: number;
    end: number;
}

function minimumIntervalsCover(
    intervals: Interval[],
    targetStart: number,
    targetEnd: number
): Interval[] | null {
    const sorted = intervals.sort((a, b) => a.start - b.start);
    const selected: Interval[] = [];

    let currentPos = targetStart;
    let i = 0;

    while (currentPos < targetEnd) {
        let farthest = currentPos;

        while (i < sorted.length && sorted[i].start <= currentPos) {
            farthest = Math.max(farthest, sorted[i].end);
            i++;
        }

        if (farthest === currentPos) return null;

        selected.push({start: currentPos, end: farthest});
        currentPos = farthest;
    }

    return selected;
}

// Greedy Value Maximization
interface Item {
    weight: number;
    value: number;
    name: string;
}

function maximizeValue(items: Item[], weightLimit: number): {value: number, items: string[]} {
    const sorted = items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));

    let totalValue = 0;
    let totalWeight = 0;
    const selected: string[] = [];

    for (const item of sorted) {
        if (totalWeight + item.weight <= weightLimit) {
            selected.push(item.name);
            totalWeight += item.weight;
            totalValue += item.value;
        }
    }

    return {value: totalValue, items: selected};
}

const activities: Activity[] = [
    {start: 1, end: 3, name: 'A'},
    {start: 2, end: 5, name: 'B'},
    {start: 4, end: 6, name: 'C'},
    {start: 6, end: 9, name: 'D'},
    {start: 5, end: 7, name: 'E'}
];
console.log(activitySelection(activities));

const intervals: Interval[] = [
    {start: 1, end: 3},
    {start: 2, end: 5},
    {start: 3, end: 7},
    {start: 5, end: 9},
    {start: 8, end: 10}
];
console.log(minimumIntervalsCover(intervals, 1, 10));

const items: Item[] = [
    {weight: 2, value: 10, name: 'item1'},
    {weight: 3, value: 20, name: 'item2'},
    {weight: 5, value: 30, name: 'item3'}
];
console.log(maximizeValue(items, 7));

Common Pitfalls

warning

Applying greedy without verification: Greedy only works when both greedy choice property and optimal substructure hold. Test on small examples first.

Wrong sorting criterion: Greedy depends on correct prioritization. Choose sorting key based on problem analysis, not intuition.

Greedy vs DP confusion: Similar problems may require different approaches. 0/1 Knapsack needs DP; fractional knapsack works with greedy.

Ignoring constraints: Greedy becomes invalid when problem has hidden constraints. Carefully read problem statement.

Not proving correctness: Greedy correctness isn't obvious. Always verify with exchange argument or induction before using.

Off-by-one errors in intervals: Interval problems are error-prone at boundaries. Test overlap conditions carefully.

Self-Check

1. Why does activity selection work by choosing earliest-finishing activity? Can you explain using exchange argument?
2. What's the difference between greedy choice property and optimal substructure? Can one exist without the other?
3. When would you choose greedy over DP? What specific properties must problem have?

One Takeaway

info

Greedy algorithms excel when problems have greedy choice property and optimal substructure. The key is recognizing when these properties hold—most optimization problems don't satisfy both. Exchange argument provides powerful proof technique: show any other solution can be transformed into greedy solution without loss. Master activity selection pattern and you'll recognize similar structures in interval problems, resource allocation, and scheduling. Always verify greedy applicability before coding; a greedy solution is elegant only if it's correct.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson Education.