What Is Greedy? - Learning Module

Loading content...

0/276

Making the Best Local Choice at Each Step

The Art of Optimal Selection

At the heart of every greedy algorithm lies a deceptively simple operation: selection. At each step, the algorithm surveys available options and selects the "best" one according to some criterion. This selection is immediate, confident, and irrevocable.

But what does "best" mean? How do we define and compute it? And why does selecting the "best" at each step sometimes lead to the globally optimal solution while other times it leads to spectacular failure?

This page dissects the mechanics of greedy selection. We'll examine how different problems demand different selection criteria, how to compute these efficiently, and how the choice of criterion can make or break your algorithm.

What You Will Learn

By the end of this page, you will understand how to identify and implement selection criteria, recognize common greedy selection patterns, and appreciate why the definition of 'locally optimal' varies by problem. You'll gain practical skills in designing the selection phase of greedy algorithms.

The Selection Criterion: Defining 'Best'

The selection criterion (also called the greedy criterion or choice function) is the rule that determines which candidate to select at each step. This criterion is the soul of the algorithm—everything else is just mechanics.

Formally, given a set of candidates C and a partial solution S, the selection criterion is a function:

g: C × S → ℝ

The greedy algorithm selects the candidate c* that maximizes (or minimizes) g(c, S):

c* = argmax_{c ∈ C} g(c, S)

Types of Selection Criteria

•Single-Attribute Criteria — Selection based on one property: largest value, smallest weight, earliest deadline. Simple but often effective.
•Ratio Criteria — Selection based on a ratio of attributes: value/weight, profit/time, benefit/cost. Common in resource allocation problems.
•State-Dependent Criteria — Selection depends on the current partial solution: element that fits best given what's already chosen, node closest to current path.
•Derived Criteria — Selection based on computed properties: element that maximizes marginal gain, minimizes regret, or satisfies the most constraints.

The Criterion Determines Correctness

Two greedy algorithms for the same problem that differ only in their selection criterion can have completely different correctness properties. One might be optimal, the other arbitrarily bad. The criterion is not a minor implementation detail—it's the algorithm's defining characteristic.

Example: The Activity Selection Problem

Consider scheduling non-overlapping activities to maximize the number selected. Each activity has a start time and end time.

Multiple selection criteria seem reasonable:

Earliest Start Time — Select the activity that starts first
Shortest Duration — Select the activity with minimal (end - start)
Earliest End Time — Select the activity that finishes first
Fewest Conflicts — Select the activity that overlaps with the fewest others

Remarkably, only Earliest End Time is guaranteed optimal. The others can all fail:

Earliest Start: An early activity might block many later ones
Shortest Duration: A short activity might occur in the middle, blocking activities on both sides
Fewest Conflicts: Counterexamples exist where this fails

The "right" criterion isn't always intuitive. It must be proven correct.

Common Selection Patterns in Practice

Across the landscape of greedy problems, certain selection patterns recur. Recognizing these patterns accelerates problem-solving and provides intuition for new problems.

Common Greedy Selection Patterns
Pattern	Selection Rule	Example Problems	Intuition
Extreme Value	Largest or smallest element	Coin change (canonical), task scheduling	Extremes "cover" more or leave room for more
Earliest Deadline	Item with closest deadline	Activity selection, task scheduling with deadlines	Handle urgent items first to avoid misses
Best Ratio	Maximize value/cost ratio	Fractional knapsack, scheduling with weights	Get maximum "bang for buck"
Nearest Neighbor	Closest unvisited element	TSP approximation, clustering	Minimize immediate cost; hope path remains good
Maximum Marginal	Largest improvement to current solution	Set cover greedy, feature selection	Each step makes maximum possible progress
Minimum Regret	Choice with lowest opportunity cost	Some scheduling variants	Minimize what you give up by choosing

Pattern Deep-Dive: The Ratio Pattern

The ratio pattern deserves special attention because it appears in many optimization problems and has subtle correctness considerations.

Fractional Knapsack: Items have weights and values. You can take fractions of items. Selection criterion: value/weight ratio (descending).

Why does this work?

Each "unit" of capacity should be filled with maximum value. By taking items in decreasing value/weight order, every unit of knapsack space earns the maximum possible value.

0/1 Knapsack: Same setup, but items must be taken whole or not at all. Greedy by ratio FAILS.

Why does the same criterion fail?

In fractional knapsack, we can always use all capacity optimally. In 0/1, a high-ratio small item might prevent using a lower-ratio large item that, together with other items, would be better overall. The "lumpiness" of whole items creates interference between choices.

fractional_knapsack_greedy.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from dataclasses import dataclass
 
@dataclass
class Item:
    weight: float
    value: float
    
    @property
    def ratio(self) -> float:
        return self.value / self.weight if self.weight > 0 else float('inf')
 
 
def fractional_knapsack(items: list[Item], capacity: float) -> float:
    """
    Greedy algorithm for fractional knapsack.
    Selection criterion: value/weight ratio (highest first)
    
    Time: O(n log n) for sorting, O(n) for selection
    Space: O(n) for sorted copy
    
    PROVABLY OPTIMAL for fractional knapsack.
    """
    # Sort by ratio in descending order
    sorted_items = sorted(items, key=lambda x: x.ratio, reverse=True)
    
    total_value = 0.0
    remaining_capacity = capacity
    
    for item in sorted_items:
        if remaining_capacity <= 0:
            break
            
        # Take as much of this item as possible
        take_weight = min(item.weight, remaining_capacity)
        take_fraction = take_weight / item.weight
        take_value = take_fraction * item.value
        
        total_value += take_value
        remaining_capacity -= take_weight
        
        # Debug: Show what we're taking
        if take_fraction < 1:
            print(f"Taking {take_fraction:.2%} of item "
                  f"(w={item.weight}, v={item.value}, ratio={item.ratio:.2f})")
        else:
            print(f"Taking 100% of item "
                  f"(w={item.weight}, v={item.value}, ratio={item.ratio:.2f})")
    
    return total_value
 
 
# Example
items = [
    Item(weight=10, value=60),   # ratio = 6.0
    Item(weight=20, value=100),  # ratio = 5.0
    Item(weight=30, value=120),  # ratio = 4.0
]
capacity = 50
 
result = fractional_knapsack(items, capacity)
print(f"\nMaximum value: {result}")
# Takes all of item 1 (10kg, value 60)
# Takes all of item 2 (20kg, value 100)
# Takes 2/3 of item 3 (20kg, value 80)
# Total: 50kg, value 240

Implementing Efficient Selection

Selection must be efficient for a greedy algorithm to achieve its potential. If we take O(n) time to select each of n items, we get O(n²) overall—often no better than brute force. The implementation strategy for selection directly impacts the algorithm's time complexity.

Selection Implementation Strategies

•Pre-Sorting — Sort candidates by the selection criterion before the main loop. Selection becomes O(1) (next element), total O(n log n). Best when the criterion doesn't depend on the partial solution.
•Priority Queue / Heap — Use a heap when candidates are added/removed dynamically or when priorities change. Selection O(log n), total O(n log n).
•Indexed Data Structures — For specialized queries (nearest neighbor, range queries), use trees, segment trees, or spatial indices. Selection may be O(log n) or O(1) with preprocessing.
•Lazy Evaluation — Compute criterion values on demand rather than upfront. Useful when most candidates won't be considered.

efficient_selection_patterns.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import heapq
from typing import TypeVar, Callable, Iterable
 
T = TypeVar('T')
 
# Pattern 1: Pre-Sorting
# Use when: Criterion is static (doesn't depend on current solution)
# Example: Activity selection by end time
 
def greedy_with_presort(
    candidates: list[T],
    key: Callable[[T], float],
    is_feasible: Callable[[T, list[T]], bool]
) -> list[T]:
    """
    Generic greedy with pre-sorting.
    
    Time: O(n log n) sorting + O(n) selection = O(n log n)
    Space: O(n) for sorted copy
    """
    sorted_candidates = sorted(candidates, key=key)
    solution = []
    
    for candidate in sorted_candidates:
        if is_feasible(candidate, solution):
            solution.append(candidate)
    
    return solution
 
 
# Pattern 2: Priority Queue (Heap)
# Use when: Candidates added dynamically or priorities change
# Example: Dijkstra's algorithm
 
def greedy_with_heap(
    initial_candidates: Iterable[tuple[float, T]],
    process: Callable[[T, list], list[tuple[float, T]]],
    is_complete: Callable[[list[T]], bool]
) -> list[T]:
    """
    Generic greedy with priority queue.
    
    Each process() can add new candidates to the queue.
    Time: O((V + E) log V) for graph problems
    """
    heap = list(initial_candidates)
    heapq.heapify(heap)
    solution = []
    visited = set()
    
    while heap and not is_complete(solution):
        priority, candidate = heapq.heappop(heap)
        
        if candidate in visited:
            continue
        visited.add(candidate)
        solution.append(candidate)
        
        # Processing might add new candidates
        new_candidates = process(candidate, solution)
        for new_priority, new_candidate in new_candidates:
            if new_candidate not in visited:
                heapq.heappush(heap, (new_priority, new_candidate))
    
    return solution
 
 
# Pattern 3: Union-Find for Connectivity
# Use when: Selection depends on component membership
# Example: Kruskal's MST algorithm
 
class UnionFind:
    """Efficient disjoint set for Kruskal-style selection."""
    
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        """Returns True if x and y were in different components."""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # Same component, would create cycle
        
        # Union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        
        return True
 
 
def kruskal_mst(n: int, edges: list[tuple[int, int, float]]) -> list[tuple[int, int, float]]:
    """
    Kruskal's MST using pre-sorting + Union-Find.
    
    Time: O(E log E) sorting + O(E α(V)) union-find ≈ O(E log E)
    """
    sorted_edges = sorted(edges, key=lambda e: e[2])  # Sort by weight
    uf = UnionFind(n)
    mst = []
    
    for u, v, weight in sorted_edges:
        if uf.union(u, v):  # O(α(n)) amortized
            mst.append((u, v, weight))
            if len(mst) == n - 1:
                break  # MST complete
    
    return mst

Choose the Right Data Structure

The efficiency of greedy selection hinges on using the right data structure. Pre-sorting is simplest and often sufficient. Priority queues handle dynamic scenarios. Union-Find enables efficient cycle detection for spanning tree problems. Matching the data structure to the problem pattern is critical for optimal performance.

The Commitment Process: Why No Backtracking

What distinguishes greedy from backtracking is the commitment: once a choice is made, it's final. This irrevocability is both the source of greedy's efficiency and the reason it can fail.

Why the commitment matters:

Commitment enables:

Linear Scans — Each candidate is considered at most once
No State Explosion — No need to track alternative solution paths
Simple Implementation — No recursion stack, no rollback logic
Predictable Performance — Running time is straightforward to analyze

Commitment requires:

Correctness Guarantee — We must KNOW (prove) that the greedy choice is safe
Irrevocable Feasibility — Adding the choice must not create future infeasibility

Greedy: Commitment Model

•Make choice → Commit forever
•No alternative paths explored
•Each candidate processed once
•Linear or linearithmic time
•Requires correctness proof

Backtracking: Exploration Model

•Try choice → Explore → Maybe undo
•All viable paths explored
•Candidates revisited many times
•Often exponential time
•Correctness via exhaustive search

The Mechanics of Commitment:

In code, commitment manifests in several ways:

Removal from candidate set — The selected element is removed so it's never reconsidered
State updates — Global state (remaining capacity, current position, active components) is modified irrevocably
Constraint propagation — Selection may make other candidates infeasible
Progress invariants — Each step brings us closer to a complete solution

Example: Job Scheduling with Deadlines

We have jobs with profits and deadlines. At each step, we commit to scheduling a job in a time slot. Once committed:

That time slot becomes unavailable
The remaining problem has fewer slots and fewer jobs
We never reconsider which job fills that slot

If our selection criterion is correct (e.g., highest profit job that can still meet its deadline), commitment works. If incorrect, commitment locks in suboptimal choices.

When to Reconsider Commitment

If you find yourself wanting to undo greedy choices, the problem likely requires backtracking or DP, not greedy. Greedy with 'maybe I'll change this later' is no longer greedy—it's heuristic search. Be honest about which paradigm your algorithm actually uses.

Selection Pitfalls: When Intuition Fails

Even with a good understanding of greedy principles, selection criteria can be tricky. Here are common pitfalls and how to avoid them.

Common Selection Pitfalls

•Confusing 'obviously good' with 'provably optimal' — The largest item seems valuable, but it might block better combinations. Always verify with adversarial examples.
•Ignoring constraint interactions — Selecting based on one attribute may conflict with constraints on another. Example: Highest value might also be highest weight, exceeding capacity.
•Horizon blindness — The best immediate choice might preclude better future choices. Classic example: taking $4 now when waiting allows $5 later.
•Tie-breaking arbitrarily — When multiple candidates have equal criterion values, the tie-breaking rule matters. Some tie-breakers preserve optimality; others don't.
•Optimizing the wrong objective — Make sure the selection criterion actually relates to the problem objective. Minimizing distance doesn't always minimize cost.

Case Study: The Trap of Maximum Immediate Gain

Consider a path-finding problem where each edge has two costs: immediate cost and maintenance cost. A greedy algorithm that always takes the minimum immediate cost edge might lead to a path with enormous total maintenance costs.

The correct approach might be:

Greedy by total edge cost (immediate + maintenance)
Greedy by ratio: immediate cost / maintenance savings
Not greedy at all: Requires DP or optimization

The lesson: understand what you're optimizing before designing the criterion.

selection_pitfall_example.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
Demonstration: How wrong selection criteria lead to suboptimal solutions.
 
Problem: Select items to maximize total value with total weight ≤ capacity.
"""
 
def greedy_by_value(items: list[tuple[int, int]], capacity: int) -> int:
    """Greedy by highest value first. WRONG for general case."""
    sorted_items = sorted(items, key=lambda x: x[0], reverse=True)
    total_value = 0
    remaining = capacity
    
    for value, weight in sorted_items:
        if weight <= remaining:
            total_value += value
            remaining -= weight
    
    return total_value
 
 
def greedy_by_ratio(items: list[tuple[int, int]], capacity: int) -> int:
    """Greedy by value/weight ratio. STILL WRONG for 0/1 knapsack."""
    sorted_items = sorted(
        items, 
        key=lambda x: x[0]/x[1] if x[1] > 0 else float('inf'), 
        reverse=True
    )
    total_value = 0
    remaining = capacity
    
    for value, weight in sorted_items:
        if weight <= remaining:
            total_value += value
            remaining -= weight
    
    return total_value
 
 
# Counter-example showing both greedy approaches fail
items = [
    (100, 50),  # High value, high weight, ratio = 2.0
    (60, 20),   # Medium value, low weight, ratio = 3.0
    (60, 20),   # Same as above
]
capacity = 50
 
print("0/1 Knapsack Counterexample")
print(f"Items: {items}")
print(f"Capacity: {capacity}")
print()
print(f"Greedy by value: {greedy_by_value(items, capacity)}")  # Takes (100,50) → 100
print(f"Greedy by ratio: {greedy_by_ratio(items, capacity)}")  # Takes 2×(60,20) → 120
print(f"Optimal (DP): 120")  # Two medium items beat one large
print()
print("In this case, greedy by ratio happens to work.")
print("But there exist cases where BOTH criteria fail!")
 
# Another counter-example
items2 = [
    (50, 30),   # ratio = 1.67
    (40, 25),   # ratio = 1.60
    (30, 20),   # ratio = 1.50
]
capacity2 = 50
 
print()
print(f"Items: {items2}")
print(f"Capacity: {capacity2}")
print(f"Greedy by ratio: {greedy_by_ratio(items2, capacity2)}")  # Takes (50,30) → can't fit others → 50
print(f"Optimal: 70")  # Take (40,25) + (30,20) = capacity 45, value 70

Never Trust Intuition Alone

These examples show that even 'reasonable' criteria can fail. Greedy by value, greedy by ratio, greedy by weight—all fail for 0/1 knapsack. The problem structure simply doesn't support greedy. No selection criterion fixes this; you need a different paradigm (DP).

A Framework for Designing Selection Criteria

Given a new problem, how do you design the selection criterion? Here's a systematic framework:

Selection Criterion Design Framework

•Identify the objective — What are we maximizing or minimizing? Be precise: total value? count? distance? time?
•List candidate criteria — Brainstorm multiple selection rules. Consider: direct attributes, ratios, derived quantities, extremes.
•For each criterion, seek counterexamples — Try to construct inputs where the criterion fails. Start with small cases (3-4 elements).
•Analyze why failures occur — Does the criterion ignore important constraints? Does it optimize a proxy instead of the real objective?
•Refine or eliminate criteria — Adjust criteria that 'almost work' or eliminate those with fundamental flaws.
•Attempt correctness proof — For surviving criteria, try to prove the greedy choice property. If proof fails, criterion is wrong.
•If no criterion survives — The problem may not admit a greedy solution. Consider DP or other approaches.

Example Walkthrough: Meeting Room Scheduling

Problem: Schedule maximum non-overlapping meetings in a single room.

Step 1: Objective — Maximize count of meetings.

Step 2: Candidate Criteria

Shortest meeting first
Earliest start time first
Earliest end time first
Latest start time first

Step 3: Seek Counterexamples

Shortest meeting: Meetings: [1-5], [2-3], [4-10] Shortest: [2-3] (duration 1) After choosing [2-3]: Can only add [4-10] Total: 2 meetings Optimal: [1-5], [5-10] variant or similar—wait, [1-5] overlaps [2-3]...

Actually, taking shortest [2-3] → [4-10] gives 2 meetings. Taking [1-5] → can't take [2-3] → can take [4-10]? No, [1-5] overlaps [4-10] at t=4-5.

Let me try: [1-4], [2-3], [3-6] Shortest: [2-3] (dur 1) — blocks both others Optimal: [1-4], [4-6] = {[1-4]} only since [3-6] overlaps.

Better counterexample for shortest: [1-2], [2-3], [1-3] Shortest: [1-2] or [2-3] (dur 1 each) Taking [1-2] → can add [2-3] → 2 meetings Taking [1-3] → duration 2 → alone → 1 meeting Shortest works here...

Actual counterexample for shortest: [0-6], [1-2], [3-5], [7-8] Shortest = [1-2] or [3-5] or [7-8] (dur 1 each) If we sort by duration: [1-2], [3-5], [7-8], [0-6] Taking [1-2] → can't take [0-6] → take [3-5] → take [7-8] → 3 meetings ✓ [0-6] would block [1-2] and [3-5], giving only [0-6], [7-8] = 2 meetings.

Shortest seems okay... but there exist counterexamples: [0-2], [1-3], [2-4] All duration 2. Earliest ending [0-2] → can take [2-4] → 2 meetings. Shortest just picks first equal, same as earliest end. No help.

Step 4: Earliest End Time

This is the known optimal criterion. Proof sketch:

Taking the earliest-ending meeting M1 leaves maximum room after
Any optimal solution O* either contains M1 or contains some M' that ends later
If O* has M' instead of M1, we can swap M' for M1 without losing optimality
By induction, greedy by earliest end time is optimal.

Step 5-7: Earliest end time survives; others have counterexamples or no proof.

Practice Building Counterexamples

The ability to construct counterexamples is crucial for greedy algorithm design. Start with minimal cases: 2-3 elements, minimal constraints. If a criterion is wrong, there's usually a small counterexample. Finding it quickly saves hours of debugging.

Selection in Multi-Stage Problems

Some problems require multiple different selection criteria at different stages, or the criterion changes as the solution evolves. These multi-stage greedy algorithms are more complex but still follow greedy principles.

Example: Two-Phase Activity Selection

Consider a variant where activities have both value and duration. We want to:

Maximize the number of activities (primary objective)
Among solutions with maximum count, maximize total value (secondary)

Two-Phase Approach:

Phase 1: Use earliest-end-time to maximize count
Phase 2: Among activities with equal end times, prefer higher value

This maintains greedy's efficiency while handling multiple objectives.

multi_stage_greedy.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from dataclasses import dataclass
from typing import Callable
 
@dataclass
class Activity:
    id: str
    start: int
    end: int
    value: int
 
 
def multi_objective_activity_selection(activities: list[Activity]) -> list[Activity]:
    """
    Two-objective greedy: 
    1. Maximize count (primary) using earliest-end-time
    2. Maximize value (secondary) using value as tiebreaker
    
    Selection criterion: (end_time, -value) — sort ascending
    Earliest end wins; among ties, highest value wins.
    """
    # Multi-key sort: primary = end time (asc), secondary = value (desc)
    sorted_activities = sorted(
        activities, 
        key=lambda a: (a.end, -a.value)
    )
    
    selected = []
    last_end = float('-inf')
    
    for activity in sorted_activities:
        if activity.start >= last_end:  # Non-overlapping
            selected.append(activity)
            last_end = activity.end
    
    return selected
 
 
# Example
activities = [
    Activity("A", 0, 3, 10),
    Activity("B", 0, 3, 20),  # Same interval as A, higher value
    Activity("C", 2, 5, 15),
    Activity("D", 3, 7, 25),
    Activity("E", 5, 8, 30),
    Activity("F", 6, 9, 10),
]
 
result = multi_objective_activity_selection(activities)
print("Selected activities:")
for a in result:
    print(f"  {a.id}: [{a.start}-{a.end}] value={a.value}")
print(f"Count: {len(result)}, Total Value: {sum(a.value for a in result)}")
 
# Output:
# B is chosen over A (same time, higher value)
# Then D (starts at 3, after B ends)
# Then E or F (E ends earlier, same time, E has higher value)

State-Dependent Selection:

Some criteria depend on the current state of the solution:

Dijkstra's algorithm: Next vertex is the one with minimum distance from the current frontier
Prim's algorithm: Next edge is the minimum edge connected to the current tree
Huffman coding: Merge the two nodes with minimum frequency currently in the forest

These require dynamic data structures (heaps, priority queues) because the "best" choice changes as the solution grows.

Dynamic vs Static Criteria

Static criteria (pre-sortable) lead to simpler, faster algorithms. Dynamic criteria (state-dependent) require priority queues but handle more complex problems. Recognize which type your problem needs before choosing implementation strategy.

Summary: Making the Best Local Choice

We've deeply explored the mechanics of greedy selection. Let's consolidate the key insights:

Key Takeaways

•Selection criterion is the algorithm's soul — The definition of 'best' determines correctness. Different criteria for the same problem can be optimal or arbitrarily bad.
•Common patterns exist — Extreme values, best ratios, earliest deadlines, nearest neighbors. Recognize patterns to accelerate design.
•Efficient implementation matters — Pre-sorting for static criteria, heaps for dynamic criteria. Data structure choice determines complexity.
•Commitment is irrevocable — Once selected, a choice is final. This enables efficiency but requires correctness guarantees.
•Intuition fails often — 'Obviously good' criteria frequently fail. Always verify with counterexamples and proofs.
•Systematic design helps — Follow the framework: identify objective, enumerate criteria, seek counterexamples, prove survivors.

What's Next:

We've seen how greedy algorithms select the best candidate and commit to it. But greedy's power comes paired with constraints: no backtracking, no looking ahead. The next page explores these constraints—why they exist, how they enable efficiency, and what they cost us.

Page Complete

You now understand the mechanics of greedy selection: how to design criteria, implement them efficiently, and avoid common pitfalls. Next, we'll explore the philosophical constraints—no backtracking, no looking ahead—that define greedy's character.