Greedy Algorithms:
Main Ideas
Different Algorithm Categories
❖ Greedy Algorithms
❖ Divide-and-Conquer
❖ Dynamic Programming
❖ Iterative Improvement
❖ Brute Force
Optimization Problems
For most optimization problems you want to
find, not just a solution, but the best solution.
A greedy algorithm sometimes works well for
optimization problems. It works in phases. At
each phase:
You take the best you can get right now,
without regard for future consequences.
You hope that by choosing a local
optimum at each step, you will end up at a
global optimum.
Greedy Algorithm
❖ Greedy Algorithm is defined as a method
for solving optimization problems by
taking decisions that result in the most
evident and immediate benefit irrespective
of the final outcome.
❖ It works for cases where minimization or
maximization leads to the required
solution.
The general structure of a greedy algorithm can be
summarized in the following steps:
❖ Identify the problem as an optimization problem where we need to
find the best solution among a set of possible solutions.
❖ Determine the set of feasible solutions for the problem.
❖ Identify the optimal substructure of the problem, meaning that the
optimal solution to the problem can be constructed from the
optimal solutions of its subproblems.
❖ Develop a greedy strategy to construct a feasible solution step by
step, making the locally optimal choice at each step.
❖ Prove the correctness of the algorithm by showing that the locally
optimal choices at each step lead to a globally optimal solution.
Greedy Algorithm
The local decisions (or choices) must possess
three characteristics as mentioned below:
1. Feasibility: The selected choice must fulfil
local constraints.
2. Optimality: The selected choice must be the
best at that stage (locally optimal choice).
[Link]: The selected choice cannot be
changed once it is made
Learning objectives
Come up with a greedy algorithm
yourself
Job Interview
Job Interview
Job Interview
Job Interview
Largest Number
Toy problem
What is the largest number that consists of
digits 3, 9, 5, 9, 7, 1? Use all the digits.
Largest Number
Toy problem
What is the largest number that consists of
digits 3, 9, 5, 9, 7, 1? Use all the digits.
Examples
359179, 537991, 913579, . . .
Correct answer
997531
Greedy Strategy
5 7 3 9 1 9
Greedy Strategy
Find max
5 7 3 9 1 9
Find max digit
Greedy Strategy
Find max
5 7 3 9 1 9 9
Append
Find max digit
Append it to the number
Greedy Strategy
Find max
5 7 3 9 1 9 9
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Greedy Strategy
Find max
5 7 3 1 9 9
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Greedy Strategy
Find max
5 7 3 1 9 9
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 7 3 1 9 9
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 7 3 1 9 9 9
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 7 3 1 9 9 9
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 7 3 1 9 9
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 7 3 1 9 9
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 7 3 1 9 9 7
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 7 3 1 9 9 7
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 3 1 9 9 7
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 3 1 9 9 7
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 3 1 9 9 7 5
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
5 3 1 9 9 7 5
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
3 1 9 9 7 5
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
3 1 9 9 7 5
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
3 1 9 9 7 5 3
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
3 1 9 9 7 5 3
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
1 9 9 7 5 3
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
1 9 9 7 5 3
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
1 9 9 7 5 3 1
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
1 9 9 7 5 3 1
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
Find max
9 9 7 5 3 1
Remove Append
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Greedy Strategy
5 7 3 9 1 9 9 9 7 5 3 1
Find max digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list
Car Fueling
Distance with full tank = 400km
Car Fueling
Distance with full tank = 400km
0km 950km
A B
Car Fueling
Distance with full tank = 400km
0km 200km 375km 550km 750km 950km
A B
Car Fueling
Distance with full tank = 400km
0km 200km 375km 550km 750km 950km
A B
Car Fueling
Distance with full tank = 400km
0km 200km 375km 550km 750km 950km
A B
Car Fueling
Distance with full tank = 400km
0km 200km 375km 550km 750km 950km
A B
Minimum number of refills = 2
Car Fueling
Input: A car which can travel at most L
kilometers with full tank, a source
point A, a destination point B and
n gas stations at distances
x1 ≤ x2 ≤ x3 ≤ · · · ≤ xn in
kilometers from A along the path
from A to B.
Output: The minimum number of refills to
get from A to B, besides refill at A.
Greedy Strategy
Make some greedy choice
Reduce to a smaller problem
Iterate
Greedy Choice
Refill at the the closest gas station
Refill at the farthest reachable gas
station
Go until there is no fuel
Greedy Choice
Refill at the the closest gas station
Refill at the farthest reachable gas
station
Go until there is no fuel
Greedy Algorithm
Start at A
Greedy Algorithm
Start at A
Refill at the farthest reachable gas
station G
Greedy Algorithm
Start at A
Refill at the farthest reachable gas
station G
Make G the new A
Greedy Algorithm
Start at A
Refill at the farthest reachable gas
station G
Make G the new A
Get from new A to B with minimum
number of refills
Definition
Subproblem is a similar problem of smaller
size.
Subproblem
Examples
LargestNumber(3, 9, 5, 9, 7, 1) =
Subproblem
Examples
LargestNumber(3, 9, 5, 9, 7, 1) =
‘‘ 9 ’’ +
Subproblem
Examples
LargestNumber(3, 9, 5, 9, 7, 1) =
‘‘ 9 ’’ + LargestNumber(3, 5, 9, 7, 1)
Subproblem
Examples
LargestNumber(3, 9, 5, 9, 7, 1) =
‘‘ 9 ’’ + LargestNumber(3, 5, 9, 7, 1)
Min number of refills from A to B =
Subproblem
Examples
LargestNumber(3, 9, 5, 9, 7, 1) =
‘‘ 9 ’’ + LargestNumber(3, 5, 9, 7, 1)
Min number of refills from A to B =
first refill at G +
Subproblem
Examples
LargestNumber(3, 9, 5, 9, 7, 1) =
‘‘ 9 ’’ + LargestNumber(3, 5, 9, 7, 1)
Min number of refills from A to B =
first refill at G + min number of refills
from G to B
Safe Move
Definition
A greedy choice is called safe move if there is
an optimal solution consistent with this first
move.
Lemma
To refill at the farthest reachable gas station
is a safe move.
Proof
A B
Proof
G1
A B
Proof
G1 G
A B
Proof
G1 G
A B
First case: G is closer than G2
Proof
G1 G G2
A B
First case: G is closer than G2
Proof
G1 G G2
A B
First case: G is closer than G2
Refill at G instead of G1
Proof
G1 G G2
A B
First case: G is closer than G2
Refill at G instead of G1
Proof
G1 G
A B
Second case: G2 is closer than G
Proof
G1 G2 G
A B
Second case: G2 is closer than G
Proof
G1 G2 G
A B
Second case: G2 is closer than G
Avoid refill at G1
Proof
G1 G2 G
A B
Second case: G2 is closer than G
Avoid refill at G1
Proof
G1 G2 G
A B
Second case: G2 is closer than G
Avoid refill at G1
Proof
Route R with the minimum number of
refills
Proof
Route R with the minimum number of
refills
G1 — position of first refill in R
Proof
Route R with the minimum number of
refills
G1 — position of first refill in R
G2 — next stop in R (refill or B)
Proof
Route R with the minimum number of
refills
G1 — position of first refill in R
G2 — next stop in R (refill or B)
G — farthest refill reachable from A
Proof
Route R with the minimum number of
refills
G1 — position of first refill in R
G2 — next stop in R (refill or B)
G — farthest refill reachable from A
If G is closer than G2, refill at G instead
of G1
Proof
Route R with the minimum number of
refills
G1 — position of first refill in R
G2 — next stop in R (refill or B)
G — farthest refill reachable from A
If G is closer than G2, refill at G instead
of G1
Otherwise, avoid refill at G1
A = x0 ≤ x1 ≤ x2 ≤ · · · ≤ xn ≤ xn+1 = B
MinRefills(x, n, L)
numRefills ← 0 , currentRefill ← 0
lastRefill ← currentRefill
while (currentRefill ≤ n and
x [currentRefill + 1] − x [lastRefill ] ≤ L):
currentRefill ← currentRefill + 1
i f currentRefill == lastRefill :
r e t u r n IMPOSSIBLE
i f currentRefill ≤ n :
numRefills ← numRefills + 1
r e t u r n numRefills
Lemma
The running time of MinRefills(x, n, L) is
O(n).
Lemma
The running time of MinRefills(x, n, L) is
O(n).
Proof
currentRefill changes from 0 to n + 1,
one-by-one
Lemma
The running time of MinRefills(x, n, L) is
O(n).
Proof
currentRefill changes from 0 to n + 1,
one-by-one
numRefills changes from 0 to at most n,
one-by-one
Lemma
The running time of MinRefills(x, n, L) is
O(n).
Proof
currentRefill changes from 0 to n + 1,
one-by-one
numRefills changes from 0 to at most n,
one-by-one
Thus, O(n) iterations
Reduction to Subproblem
Make a first move
Then solve a problem of the same kind
Smaller: fewer digits, fewer fuel stations
This is called a “subproblem”
Safe move
A move is called safe if there is an
optimal solution consistent with this
first move
Safe move
A move is called safe if there is an
optimal solution consistent with this
first move
Not all first moves are safe
Safe move
A move is called safe if there is an
optimal solution consistent with this
first move
Not all first moves are safe
Often greedy moves are not safe
General Strategy
Problem
General Strategy
greedy choice
Problem
Make a greedy choice
General Strategy
greedy choice
Problem Safe move
Make a greedy choice
Prove that it is a safe move
General Strategy
greedy choice
Problem Safe move
Subproblem
Make a greedy choice
Prove that it is a safe move
Reduce to a subproblem
General Strategy
greedy choice
Problem Safe move
Subproblem
Make a greedy choice
Prove that it is a safe move
Reduce to a subproblem
Solve the subproblem
Advantages of Greedy Algorithm
❖ The greedy approach is easy to implement.
❖ Typically have less time complexity.
❖ Greedy algorithms can be used for optimization
purposes or finding close to optimization in case
of Hard problems.
❖ Greedy algorithms can produce efficient
solutions in many cases, especially when the
problem has a substructure that exhibits the
greedy choice property.
Advantages of Greedy Algorithm
❖ The greedy approach is easy to implement.
❖ Typically have less time complexity.
❖ Greedy algorithms can be used for optimization
purposes or finding close to optimization in case
of Hard problems.
❖ Greedy algorithms can produce efficient
solutions in many cases, especially when the
problem has a substructure that exhibits the
greedy choice property.
Disadvantage of Greedy Algorithm
❖ The local optimal solution may not always be globally
optimal.
❖ Greedy algorithms do not always guarantee to find the
optimal solution, and may produce suboptimal solutions in
some cases.
❖ The greedy approach relies heavily on the problem structure
and the choice of criteria used to make the local optimal
choice. If the criteria are not chosen carefully, the solution
produced may be far from optimal.
Disadvantage of Greedy Algorithm
❖ Greedy algorithms may require a lot of preprocessing to
transform the problem into a form that can be solved by the
greedy approach.
❖ Greedy algorithms may not be applicable to problems where
the optimal solution depends on the order in which the inputs
are processed.