Analysis & Design of Algorithms
Activity
Selection • Prepared by:-
Problem Sagar Virani
Assistant Professor
Computer Engineering
Department
VVP Engineering College
Activity Selection Problem
You are given:
• A set S = {a1, a2 ,…, an} of n proposed activities that wish to use a resource, such as
lecture hall, which can serve only one activity at a time.
• Each activity ai has a start time si and a finish time fi, where 0 ≤ si < fi < ∞.
• If selected, activity ai takes place during the half-open time interval [si, fi).
• Activities ai and aj are compatible if the intervals [si, fi) and [sj, fj) do not overlap i.e. ai
and aj are compatible if si ≥ fj or sj ≥ fi.
The problem states:
• We wish to select a maximum-size subset of mutually compatible activities.
• We assume that the activities are sorted in monotonically increasing order of finish time:
f1 ≤ f2 ≤ f3 ≤ …. ≤ fn – 1 ≤ fn.
Activity Selection Problem
Example:
i 1 2 3 4 5 6 7 8 9 10 11
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
• Selected Activity: a3
• Selected Activity: a9
• Selected Activity: a11
• {a3, a9, a11} consists of mutually compatible activities.
Activity Selection Problem
Example:
i 1 2 3 4 5 6 7 8 9 10 11
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
• Selected Activity: a1
• Selected Activity: a4
• Selected Activity: a8
• Selected Activity: a11
• {a1, a4, a8, a11} is a largest subset of mutually compatible activities.
Activity Selection Problem
Example:
i 1 2 3 4 5 6 7 8 9 10 11
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
• Selected Activity: a2
• Selected Activity: a4
• Selected Activity: a9
• Selected Activity: a11
• {a2, a4, a9, a11} is also a largest subset of mutually compatible activities.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
A = {a1}
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
for i = 2 to n
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
3 4
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
0 4
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
5 4
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1, a4}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
3 7
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1, a4}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
5 7
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1, a4}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
6 7
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1, a4}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
8 7
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1, a4, a8}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
8 11
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1, a4, a8}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
2 11
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1, a4, a8}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
11 11
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1, a4, a8, a11}
si 1 3 0 5 3 5 6 8 8 2 12
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
11 11
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
Activity Selection Problem
Steps for Activity Selection Problem:
i 1 2 3 4 5 6 7 8 9 10 11 A = {a1, a4, a8, a11}
si 1 3 0 5 3 5 6 8 8 2 12 Max non-overlapping activities.
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
• Step1: Select the first activity from input (sorted) ACTIVITY-SELECTOR(s, f):
array and add it to solution array. n = s.length
• Step2: Repeat steps 3 and 4 for the remaining activities A = {a1}
in input array. j=1
• Step3: If the start time of the currently selected activity is for i = 2 to n
11 11
greater than or equal to the finish time of previously if s[ i ] ≥ f[ j ]
selected activity, then add it to the solution array. A = A ∪ {ai}
j=i
• Step4: Select the next activity for the input array.
return A
• Step5: Print the solution array.
Activity Selection 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
fj 4 5 6 7 9 9 10 11 12 14 16
Algorithm:
Analysis: ACTIVITY-SELECTOR(s, f):
• As only one for loop is executed n – 1 times and n = s.length
considering the operations of comparing and union A = {a1}
takes Ө(1): j=1
• The running time of ACTIVITY-SELECTOR = Ө(n) if activity for i = 2 to n n
are sorted by their finish time. if s[ i ] ≥ f[ j ]
A = A ∪ {ai}
• The running time of ACTIVITY-SELECTOR = Ө(n lgn) if
j=i
activity are not sorted by their finish time.
return A
Activity Selection Problem
Do it yourself:
i 1 2 3 4 5 6 7
si 1 3 2 0 5 8 11
fj 3 4 5 7 9 10 12
Selected job Finish time Next job Start time s[ i ] ≥ f[ j ] A
of selected of Next job
- - - - - {a1}
1 3 2 3 3≥3 {a1, a2 }
2 4 3 2 2≥4 {a1, a2 }
2 4 4 0 0≥4 {a1, a2 }
2 4 5 5 5≥4 {a1, a2, a5}
5 9 6 8 8≥9 {a1, a2, a5}
5 9 7 11 11 ≥ 9 {a1, a2, a5, a7 }
Activity Selection Problem
Do it yourself:
i 1 2 3 4 5 6 Sort by
finish time
i 1 2 3 4 5 6
si 0 3 1 5 5 8 si 1 3 0 5 5 8
fj 6 4 2 9 7 9 fj 2 4 6 7 9 9
Selected job Finish time Next job Start time s[ i ] ≥ f[ j ] A
of selected of Next job
- - - - - {a1}
1 2 2 3 3≥2 {a1, a2 }
2 4 3 0 0≥4 {a1, a2 }
2 4 4 5 5≥4 {a1, a2, a4 }
2 7 5 5 5≥7 {a1, a2, a4}
5 7 6 8 8≥7 {a1, a2, a4, a6}
Activity Selection Problem
Applications:
• Scheduling events in a room having multiple competing events.
• Scheduling and manufacturing multiple products having their time of production on
the same machine.
• Scheduling meetings in one room.
• Several use cases in Operations Research.
Any Questions?
