Greedy Methods

The Central Idea

A greedy algorithm repeatedly makes a choice that appears best at the current moment.

It does not usually reconsider earlier decisions.

The central question is:

When does repeatedly choosing the locally best option produce a globally best solution?

Local and Global Optimality

A local choice is judged using the information available at the current step.

A global optimum is the best complete solution among all feasible solutions.

Greedy methods are successful when the local rule preserves the possibility of reaching a global optimum.

A Greedy Algorithm Has a Choice Rule

Every greedy method needs a criterion for choosing among currently available options.

Examples include:

• choose the smallest available cost;
• choose the largest available value;
• choose the earliest finishing activity;
• choose the shortest connecting edge;
• choose the item with the best value-to-cost ratio.

The choice rule is problem-specific.

Candidate Set

The candidate set contains the objects that may be chosen as part of a solution.

For a scheduling problem, the candidates may be activities.

For a network problem, the candidates may be edges.

For a resource-allocation problem, the candidates may be items or tasks.

Feasibility

A partial or complete solution is feasible if it satisfies the problem's constraints.

A greedy algorithm cannot simply choose attractive candidates. It must also reject choices that would violate feasibility.

Thus a typical greedy step is:

1. identify the best remaining candidate;
2. test whether adding it preserves feasibility;
3. accept it if feasible;
4. otherwise reject it and continue.

Objective Function

Optimization problems usually have an objective function that measures solution quality.

The goal may be to:

• minimize total cost;
• maximize total value;
• maximize the number of accepted activities;
• minimize total distance;
• minimize completion time.

A greedy rule should be designed with this objective in mind.

Greedy Choices Are Usually Irrevocable

In a standard greedy method, once a candidate is accepted, the algorithm does not later remove it in order to explore a different combination.

This is what makes greedy methods efficient and conceptually simple.

It is also what makes them dangerous: an early poor choice can block a better later solution.

A Simple Coin Example

Suppose the available coin denominations are

cents, and we want to make \(41\) cents using as few coins as possible.

A natural greedy rule is:

Take the largest coin that does not exceed the remaining amount.

Greedy Change for 41 Cents

Start with \(41\).

Choose \(25\), leaving

Choose \(10\), leaving

Choose \(5\), leaving

Choose \(1\).

The greedy solution uses

A Greedy Rule Can Fail

Now suppose the available coin denominations are

and we want to make \(6\).

The largest-first greedy rule chooses

using \(3\) coins.

But

uses only

The natural greedy rule is not optimal for this denomination system.

Greedy Does Not Mean Guessing

A greedy algorithm is not merely "pick something that looks good."

It requires:

• a precise candidate set;
• a precise feasibility test;
• a precise choice rule;
• a precise stopping condition;
• a proof or justification when optimality is claimed.

Greedy-Choice Property

A problem has the greedy-choice property when some globally optimal solution can be reached after making the prescribed greedy choice.

Informally:

The greedy first step does not destroy all optimal solutions.

This property is one of the main reasons a greedy algorithm can be correct.

Optimal Substructure

A problem has optimal substructure when an optimal solution contains optimal solutions to appropriate smaller subproblems.

Greedy methods often rely on this property after the first choice has been fixed.

The remaining problem should have the same essential form as the original one.

Greedy Choice Plus Smaller Problem

A common greedy pattern is:

1. make one locally optimal feasible choice;
2. reduce the problem to what remains;
3. solve the smaller problem greedily;
4. combine the chosen item with the smaller solution.

This resembles recursion, although greedy algorithms may be implemented either recursively or iteratively.

Interval Scheduling

Consider activities that require exclusive use of one resource.

Each activity \(i\) has a start time

and a finish time

The goal is to select as many mutually nonoverlapping activities as possible.

A Natural Greedy Rule for Scheduling

For interval scheduling, the successful greedy rule is:

Among compatible activities, choose the one that finishes earliest.

Finishing early leaves as much future time as possible for additional activities.

Interval Scheduling Example

Suppose the activities are:

The earliest finishing activity is

After choosing \(A\), activities overlapping \(A\) are excluded.

Continuing the Scheduling Example

After \(A=(1,4)\), the next compatible activity that finishes earliest is

After \(D\), choose

The greedy schedule is

Why Earliest Finish Is Better Than Earliest Start

Choosing the activity that starts earliest may reserve the resource for a long time and block many shorter activities.

Earliest finish focuses on freeing the resource as soon as possible.

The successful greedy criterion is therefore not always the most obvious one.

Exchange Arguments

An exchange argument is a common way to prove a greedy algorithm correct.

The strategy is:

1. start with an arbitrary optimal solution;
2. show that its first choice can be replaced by the greedy choice;
3. show that the replacement does not make the solution worse;
4. conclude that some optimal solution begins with the greedy choice.

Exchange Reasoning for Interval Scheduling

Let \(G\) be the activity with earliest finish time.

Suppose an optimal schedule begins with some activity \(A\).

Because \(G\) finishes no later than \(A\),

Replacing \(A\) with \(G\) cannot reduce the time available for later activities.

Therefore, there is an optimal schedule whose first activity is \(G\).

Staying Ahead Arguments

Another greedy proof technique is a staying ahead argument.

Instead of exchanging choices, compare the greedy solution with any other solution after each step.

If the greedy partial solution is always at least as favorable according to a key measure, then it can be shown to stay ahead through completion.

Cut-and-Paste Reasoning

Some greedy proofs show that if a supposedly optimal solution violates the greedy structure, part of that solution can be replaced by a better or equally good part.

This replacement contradicts optimality or produces another optimal solution that is more compatible with the greedy rule.

Exchange reasoning is one important form of this idea.

Minimum Spanning Tree Intuition

In a connected weighted graph, a minimum spanning tree connects all vertices with minimum total edge weight and contains no cycles.

Important minimum-spanning-tree algorithms use greedy edge choices.

Their success depends on structural properties of weighted graphs, not merely on the idea "always take the cheapest edge."

Why Cheapest Edge Alone Is Not Enough

If we repeatedly choose the globally cheapest unused edge without checking feasibility, we may create a cycle before all vertices are connected.

A spanning tree must remain acyclic.

Therefore, a greedy rule for this problem must combine low cost with a feasibility condition.

Greedy Edge Selection with Feasibility

One useful pattern is:

1. consider edges from smallest weight to largest weight;
2. accept an edge if it does not create a cycle;
3. reject it otherwise;
4. continue until all vertices are connected.

A later graph-algorithms lesson will develop this method more formally.

Fractional Resource Allocation

Suppose divisible items each have value \(v_i\) and weight \(w_i\).

If fractions of items may be taken, a natural greedy score is

the value per unit of weight.

Choosing the highest ratio first is optimal for the fractional knapsack problem.

Why Divisibility Matters

In fractional knapsack, an item can be split.

If only part of the final item fits, the algorithm may take exactly the needed fraction.

This flexibility supports the greedy value-per-weight rule.

When items are indivisible, the same rule can fail.

Greedy Failure for Indivisible Items

Suppose a capacity is \(4\), and the available items are:

The value-to-weight ratios are

Greedy ratio choice takes \(A\), gaining value \(5\).

But taking \(B\) and \(C\) gives value

Greedy Algorithms Often Depend on Sorting

Many greedy algorithms begin by sorting candidates according to the greedy criterion.

Examples include:

• activities by finish time;
• edges by weight;
• items by value-to-weight ratio.

Sorting organizes the candidate set so the next greedy choice can be found efficiently.

Priority Queues

Some greedy procedures repeatedly need the currently best candidate, but candidates can change as the algorithm proceeds.

A priority queue is a data structure designed to support repeated access to a highest- or lowest-priority item.

Priority queues appear frequently in greedy graph and scheduling algorithms.

Greedy Methods and Recursion

Greedy algorithms may have a recursive interpretation:

1. make the greedy choice;
2. reduce to the remaining subproblem;
3. solve that subproblem.

However, the defining feature is not recursion itself.

The defining feature is the irrevocable locally optimal choice.

Greedy Methods and Dynamic Programming

Greedy methods and dynamic programming both attack optimization problems, but their strategies differ.

Greedy methods commit to one locally attractive choice.

Dynamic programming generally compares multiple subproblem possibilities and stores useful intermediate results.

Greedy methods are simpler when they are valid, but they are valid for fewer problem structures.

Greedy Methods and Backtracking

A greedy method commits and moves forward.

Backtracking may make a choice, later discover that it is unsuitable, undo it, and try another possibility.

This distinction is fundamental:

• greedy: commit;
• backtracking: explore and possibly reverse.

Greedy Methods Need Proof

Testing many examples can increase confidence, but it does not prove that a greedy algorithm is always optimal.

A proof should explain why the greedy choice is compatible with an optimal solution for every valid input.

Counterexamples are especially important because one failure is enough to disprove a claimed greedy rule.

Finding Counterexamples

To test a proposed greedy rule, look for situations where an attractive early choice consumes a scarce resource or blocks several valuable later choices.

Useful stress cases include:

• one large option versus several smaller options;
• short-term benefit versus long-term opportunity;
• ties in the greedy criterion;
• inputs near feasibility limits;
• nonstandard weight or coin systems.

Tie-Breaking

A greedy rule may produce ties.

If several candidates are equally good according to the local criterion, the algorithm needs either:

• a proof that any tied choice is safe;
• or a secondary tie-breaking rule.

Ignoring ties can make an algorithm underspecified.

Greedy Correctness Has Two Questions

When evaluating a greedy method, separate:

1. feasibility: does the algorithm always produce a valid solution?
2. optimality: is that valid solution always best?

A procedure can always be feasible without always being optimal.

Termination of Greedy Algorithms

Greedy procedures commonly terminate because each accepted or rejected candidate reduces the number of unprocessed candidates.

If the candidate set is finite and each step permanently handles at least one candidate, the process cannot continue indefinitely.

Efficiency of Greedy Methods

The cost of a greedy algorithm often comes from:

• sorting candidates;
• selecting the next best candidate;
• testing feasibility;
• updating the partial solution.

The greedy choice itself may be conceptually simple while the supporting data structures determine the practical efficiency.

Common Error: Assuming Local Best Means Global Best

The statement

"This is the best available choice right now"

does not imply

"This choice belongs to a globally best solution."

That implication must be justified by the structure of the problem.

Common Error: Using a Familiar Greedy Rule in a New Setting

A greedy rule that works for one class of inputs may fail after the constraints change.

Largest-coin-first works for some coin systems but not all.

Highest-value-per-weight works for fractional knapsack but not for the general indivisible version.

Greedy correctness is problem-specific.

Common Error: Ignoring Feasibility

Choosing the cheapest or most valuable candidate is meaningless if adding it violates the problem constraints.

In a spanning-tree problem, for example, adding a cheap edge that creates a cycle may be incompatible with the required structure.

Common Error: Reconsidering Choices Without Saying So

If an algorithm accepts a candidate and later removes it after exploring alternatives, the procedure is no longer a standard purely greedy method.

It may instead be using backtracking, local search, or another strategy.

Algorithm classifications depend on how choices are managed.

Common Error: Proving Only One Example

Showing that a greedy method works on one schedule, one graph, or one coin amount does not prove general correctness.

A proof must cover all inputs satisfying the problem assumptions.

A Reliable Procedure for Designing a Greedy Method

1. Identify the candidate set.
2. State the objective function.
3. State the feasibility constraints.
4. Propose a precise local-choice rule.
5. Specify how ties are handled.
6. Determine what remains after each accepted choice.
7. Test the rule on small and adversarial examples.
8. Search for a counterexample.
9. If none appears, prove the greedy-choice property or use an exchange/staying-ahead argument.
10. Analyze the supporting operations needed to implement the rule.

Example: Choosing Activities

Consider:

The earliest-finishing activity is

The earliest-finishing compatible activity after \(A\) is

Then choose

The greedy schedule is

Example: Testing a Bad Scheduling Rule

Suppose we try the rule

Choose the activity with the earliest start time.

Consider:

Earliest-start chooses \(A\) and allows only one activity.

But \(B,C,D\) are mutually compatible, giving

Therefore, earliest start is not a correct greedy criterion for maximizing the number of nonoverlapping activities.

Example: A Feasible Greedy Edge Rule

Suppose weighted edges are processed from least weight to greatest weight.

At each step:

• accept the edge if it connects two currently separate parts of the partial forest;
• reject the edge if it would create a cycle.

The feasibility test is essential: weight alone is not enough.

Practice 1: Identify the Greedy Rule

In interval scheduling, what local choice is used by the standard greedy algorithm for maximizing the number of nonoverlapping activities?

Practice 2: Coin Change

Using coin denominations

apply the largest-coin-first rule to make \(67\) cents.

Practice 3: Greedy Failure

With denominations

apply largest-coin-first to make \(6\). Then give a better solution.

Practice 4: Interval Scheduling

Select a maximum-size compatible set using earliest finish time:

Practice 5: Greedy-Choice Property

In your own words, what does the greedy-choice property say?

Practice 6: Feasibility

Why is "always choose the cheapest unused edge" incomplete as a spanning tree strategy?

Practice 7: Fractional Versus Indivisible

Why can value-per-weight greedy selection work for fractional knapsack but fail when items cannot be divided?

Practice 8: Exchange Argument

What is the purpose of an exchange argument in a greedy proof?

Practice 9: Greedy or Backtracking?

An algorithm chooses a candidate, later undoes the choice when it reaches a dead end, and then tries another candidate.

Is this behavior purely greedy?

Practice 10: Counterexample Thinking

A proposed scheduling rule says:

Always choose the activity that starts earliest.

Give a small example showing that this rule can fail to maximize the number of selected nonoverlapping activities.

Practice Answers

Practice 1

Choose the compatible activity that

Practice 2

For \(67\) cents:

The greedy method uses

Practice 3

Largest-coin-first gives

using \(3\) coins.

A better solution is

using only \(2\) coins.

Practice 4

The earliest-finishing activity is

The next compatible earliest-finishing activity is

Then choose

Thus one greedy maximum-size set is

Practice 5

It says that making the prescribed greedy choice is compatible with at least one globally optimal solution, so the greedy choice does not eliminate every optimum.

Practice 6

The cheapest unused edge may create a cycle. A spanning tree must remain acyclic, so the algorithm also needs a feasibility test.

Practice 7

Fractional knapsack allows part of an item to be taken, so capacity can be filled continuously according to value per unit weight. With indivisible items, one high-ratio choice can consume capacity that would have been better used by a combination of lower-ratio items.

Practice 8

An exchange argument shows that an optimal solution can be modified to use the greedy choice without becoming worse. This establishes that some optimal solution is compatible with the greedy decision.

Practice 9

No. Undoing choices and trying alternatives is characteristic of

rather than a purely greedy method.

Practice 10

One counterexample is

Earliest start chooses \(A\), giving only one activity, while

gives

What to Remember

• Greedy algorithms make locally attractive choices without usually reconsidering them.
• A greedy method needs a candidate set, feasibility rule, objective, and precise choice criterion.
• Local optimality does not automatically imply global optimality.
• The greedy-choice property and optimal substructure often support correctness.
• Exchange arguments and staying-ahead arguments are common greedy proof techniques.
• Earliest finish time gives an optimal greedy strategy for maximum-cardinality interval scheduling.
• A greedy rule that works in one problem setting can fail after the constraints change.
• Counterexamples are essential for testing proposed greedy rules.

The most important habit is simple: never trust a greedy rule merely because it looks locally reasonable—identify why the local choice is globally safe.

Where We Go Next

Greedy methods commit to one locally attractive choice. A different algorithmic strategy divides a problem into smaller subproblems, solves those subproblems, and combines their results.

The next lesson, Divide-and-Conquer Methods, develops problem splitting, recursive subproblems, combine steps, recursion trees, and classic examples of divide-and-conquer design.