CISC 365 - Algorithms I
W6-2: Greedy Algorithms II
Activity Selection
Ting Hu
School of Computing
Queen’s University
1© Ting Hu
2Welcome to Comic-Con
• The conference is packed with fun activities running in overlapping times
• How do we schedule our days so we can enjoy as many activities as
possible?
Start 8:00 8:30 9:50 13:00 13:20 14:30
Finish 10:00 9:20 10:40 14:30 14:10 16:00
x1 x2 x3 x4 x5 x6
3Constraint
• Selected activities must be compatible
• happens during and happens during
• and are compatible if or
• We wish to select a maximum-size subset of mutually compatible activities
xi [si, fi) xj [sj, fj)
xi xj si ≥ fj sj ≥ fi
4Recall - Greedy algorithms
• Always makes the choice that looks best at the moment
• Greedy paradigm for constrained optimization problem
- Sort the objects according to some criterion
- Repeat: select the next item under constraints until no more
selections can be made
5How to sort?
• Sort by start time
Start 9:00 9:05 9:30
Finish 10:00 9:20 10:00
x1 x2 x3
6How to sort?
• Sort by activity length, shortest first
Start 9:50 9:20 10:00
Finish 10:10 9:55 11:00
x1 x2 x3
7How to sort?
• Sort by activity length, longest first
Start 9:00 9:20 10:30
Finish 11:00 10:20 11:00
x1 x2 x3
8How to sort?
• Sort by finish time
• The idea is to pick an activity that will finish the earliest,
so we have the maximal amount of time left for others
Start 8:30 8:00 9:50 13:20 13:00 14:30
Finish 9:20 10:00 10:40 14:10 14:30 16:00
x1 x2 x3 x4 x5 x6
9The questions are
• How to formalize this algorithm?
• What is its computational complexity?
• Does it always find an optimal solution? Proof?
10
Pseudo-code algorithm
1. Sort the activities by finish time, from the earliest to
the latest
2. ActivitySelection( ):
Select
current_time = .finish_time
for to :
if .start_time current_time:
Select
current_time = .finish_time
X = {x1, x2, x3, . . . , xn}
X
x1
x1
i = 2 n
xi ≥
xi
xi
Complexity: O(n log n) + O(n) = O(n log n)
11
Proof of correctness - proof by induction
• Basis: let , the algorithm will choose no activities, which is the optimal solution
• Inductive hypothesis: Assume the algorithm ActivitySelection finds an optimal solution
when there are activities,
• Inductive proof: We need to show that the algorithm ActivitySelection can find an optimal
solution when there are activities
n = 0
k k ≥ 0
k + 1
12
• Step 1: We need to show that there is an optimal solution containing
• Step 2: We need to show that is optimal
a1
A
When there are activities,
ActivitySelection solution - Any optimal solution -
k + 1
A = {a1, a2, . . . , at} O = {o1, o2, . . . , or}
• .finish_time .finish_time .start_timea1 ≤ o1 ≤ o2 .finisha1
…
.finisho1 .starto2
• So and are compatible, thus is also an optimal solutiona1 o2 O* = {a1, o2, . . . , or}
• is an optimal solution to the reduced problem with activities starting
after finishes (inductive hypothesis), and is a solution to the same
reduced problem, so
{a2, a3, . . . , at} k
a1 {o2, . . . , or}
|{a2, a3, . . . , at} | ≥ |{o2, o3, . . . , or} |
• So , thus is an optimal solution to the problem with
activities
|A | ≥ |O* | A = {a1, a2, a3, . . . , at}
k + 1
13
Try this proof if we sort activities by start time
• Step 1: We need to show that there is an optimal solution containing
• Step 2: We need to show that is optimal
a1
A
When there are activities,
ActivitySelection solution - Any optimal solution -
k + 1
A = {a1, a2, . . . , at} O = {o1, o2, . . . , or}
• .start_time .start_timea1 ≤ o1
• Are and compatible?a1 o2
• .finish_time .start_time ??a1 ≤ o2
14
• Textbook p422, Exercise 16.1-2
• Textbook p422, Exercise 16.1-3
Exercises