GREEDY
ALGORITHMS
GREEDY
A greedy algorithm always makes the choice that looks
best at the moment
The algorithm is usually an iterative algorithm
The solution usually composed of elements. For example, a
path which composed of edges, a set which composed of
elements, etc.
In each iteration or step, the algorithm adds one
component/element to the solution set. After final step, the
solution set will be complete solution of the problem.
GREEDY ALGORITHM:
PRINCIPLES
A greedy algorithm works in phases. At each phase:
The algorithm chooses the best you can get right now, without
regard for future consequences
The algorithm hopes that by choosing a local optimum at each
step, it will end up at a global optimum
For some problems, the global optimum can be achieved
DO ALL PROBLEMS HAVE
GREEDY ALGORITHM?
The answer is ‘NO’. Only a few problems have greedy algorithms. For
example, LCS problem, Fibonacci problem, bellman ford algorithm,
mergesort, Quicksort, etc. are not greedy algorithms!
Usually, a greedy algorithm happens to be faster than other algorithms.
However, there are many exceptions. It may happen that greedy algorithm
is slower than other algorithms (e.g., dynamic algorithm) of the same
problem.
Consider the following algorithm for sorting numbers:
compute the minimum of [1. . ] and store it in
[1] compute the minimum of [2. . ] and store it
in [2] and so on
the above sorting algorithm is greedy, it has a running-time of
DO ALL PROBLEMS HAVE
GREEDY ALGORITHM?
The answer is ‘NO’. Only a few problems have greedy algorithms. For
example, LCS problem, Fibonacci problem, bellman ford algorithm,
mergesort, Quicksort, etc. are not greedy algorithms!
Usually, a greedy algorithm happens to be faster than other algorithms.
However, there are many exceptions. It may happen that greedy algorithm
is slower than other algorithms (e.g., dynamic algorithm) of the same
problem.
Consider the following algorithm for sorting numbers:
compute the minimum of [1. . ] and store it in
BTW is this
[1] compute the minimum of [2. . ] and store it
algorithm for
in [2] and so on
sorting really
greedy?
the above sorting algorithm is greedy, it has a running-time of
ACTIVITY SCHEDULING
PROBLEM
Input: A set of activities,
o Each activity has a start time and a finish time where
o By doing each job, you will get a constant amount of reward
o You want to maximize your rewards in a day
o This means you want to do as many jobs (e.g., classes) as possible
o Surely, we will do all jobs if it is possible. But job times will overlap, and it is not
possible to do all jobs.
o Some jobs will have to be sacrificed for other jobs
o Your task is to find the maximum number of doable jobs
Two activities are compatible if and only if their intervals do not overlap
Output: a maximum-size subset of mutually compatible activities
ACTIVITY SCHEDULING
PROBLEM
Formally:
Input: A set of activities,
o Given a set of activities
o = start time of activity and
o = finish time activity
o where
Find max-size subset of compatible activities
ACTIVITY SCHEDULING
PROBLEM
Formally:
Input: A set of activities,
o Given a set of activities
o = start time of activity and
o = finish time activity
o where
Find max-size subset of compatible activities
ACTIVITY SCHEDULING
PROBLEM
i 1 2 3 4 5 6
7 8 9 10 11
si 1 3 0 5 3 5
6 8 8 2 12
f 4 5 6 7 8 9
What is thei maximum number of activities that can be completed?
10 11 12 13 14
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
4
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
can be scheduled
4
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
can be scheduled
4
can also be scheduled
larger set
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
can be scheduled
4
can also be scheduled
larger set
5
can also be scheduled
another larger set
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM
The greedy choice can be applied to find solutions (the maximum number
of activities that can be performed) by using
o earliest finish time
o earliest start time
o shortest interval
ACTIVITY SCHEDULING
PROBLEM
The greedy choice can be applied to find solutions (the maximum number
of activities that can be performed) by using
o earliest finish time Always gives
optimal solution
o earliest start time
o shortest interval
ACTIVITY SCHEDULING
PROBLEM
The greedy choice can be applied to find solutions (the maximum number
of activities that can be performed) by using
o earliest finish time Always gives
optimal solution
o earliest start time
Does not always
give optimal
o shortest interval
solution
Does not always
give optimal
solution
ACTIVITY SCHEDULING: EARLY
FINISH TIME
Select the activity with the earliest finish time from the consideration list
Eliminate the activity from consideration list
Eliminate all non-compatible activities from the consideration list
Repeat unless the consideration list is empty
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
4
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
4
𝐴= {𝑎 1 }
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
4
𝐴= {𝑎 1 }
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
4
𝐴= {𝑎 1 , 𝑎 4 }
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
4
𝐴= {𝑎 1 , 𝑎 4 }
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
4
𝐴= {𝑎 1 ,𝑎 4 ,𝑎 8 }
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
4
𝐴= {𝑎 1 ,𝑎 4 ,𝑎 8 }
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING
PROBLEM 1 2 3 4 5 6 7 8 9 10 11
2
1 3 0 5 3 5 6 8 8 2 12
4 5 6 7 8 9 10 11 12 13 14
3
4
𝐴={𝑎 1 ,𝑎 4 ,𝑎 8 , 𝑎 11 }
5
6
7
8
9
11 10
1
ACTIVITY SCHEDULING: EARLY
FINISH TIME
Greedy-Activity-Scheduling ()
1 sort arrays and based on finish times
2
3
4 for to
5 if
6
7
8 return
ACTIVITY SCHEDULING: EARLY
FINISH TIME
Greedy-Activity-Scheduling ()
1 sort arrays and based on finish times
2
3
4 for to
5 if
6
7
8 return
Running time is from sorting operation
ACTIVITY SCHEDULING: EARLY
FINISH TIME
Theorem 1. The job with the earliest finish time is in an optimal solution.
We will prove this by contradiction!
Suppose that the job (say job id ) with the earliest finish time is not in
any of the optimal solutions (there can be multiple optimal solutions)
Consider arbitrarily any one of these optimal solution sets (say )
Select the job that has the earliest finish (or start time) time in this
solution set . Let, the job id of this selected job be .
Surely, because job has the earliest finish time among all jobs initially
Observer that, we can replace job with job without creating any conflict
with the other jobs in set and still remains to be optimal [same size] A
contraction to our assumption that job is not in any optimal solutions!
ACTIVITY SCHEDULING: EARLY
FINISH TIME
Prove that Greedy-Activity-Scheduling generate an optimal solution.
According theorem 1, we select the first job since it is in
optimal solution.
Then, we remove all conflicting jobs from the job set.
The original problem is then transformed to a similar problem of
smaller size.
So, we continue selecting jobs following theorem 1 and we
always remain optimal.
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 3 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 3 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 3 , 𝑎7 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 3 , 𝑎7 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴={𝑎3 , 𝑎7 , 𝑎 11 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴={𝑎3 , 𝑎7 , 𝑎 11 }
11 10 9 8 7 6 5 4 3 2
Not an optimal
solution
1
ACTIVITY SCHEDULING:
SHORTEST INTERVAL
Select the activity with the shortest interval
Eliminate the activities that could not be scheduled
Repeat!
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 2 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 3 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 3 , 𝑎11 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴={𝑎3 , 𝑎11 ,𝑎 4 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴={𝑎3 , 𝑎11 ,𝑎 4 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴={𝑎3 , 𝑎11 ,𝑎4 ,𝑎8 }
11 10 9 8 7 6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴={𝑎3 , 𝑎11 ,𝑎4 ,𝑎8 }
11 10 9 8 7 6 5 4 3 2
Gives optimal solution
in this example
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {}
6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 2 }
6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 2 , 𝑎4 }
6 5 4 3 2
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 2 , 𝑎4 }
Not an optimal
6 5 4 3 2
solution
1
ACTIVITY SCHEDULING: EARLY
START TIME
Select the activity with the earliest start
Eliminate the activities that could not be scheduled
Repeat!
𝐴= {𝑎 2 , 𝑎4 }
Not an optimal
6 5 4 3 2
solution
1
Optimal solution is
CONTENT COURTESY
Dr. Abul Kashem Mia, Professor, CSE, BUET
Sukarna Barua, Assistant Professor, CSE, BUET
