CS502
Assignment No. 3
Solution no. 1
 Activity Start time Finish time A 1 4 B 3 5 C 1 6 D 5 7 E 3 8 F 5 9 G 6 10 H 8 11 I 8 12
Let starting time of second activity = U
Finish time of first activity = V

HENCE selected activity which starts first
U >= V
First we B activity
3 >= 4
We can’t select this activity because that is not satisfied.
Check next activity C
1 >= 5
We can’t select this activity because that is not satisfied.
Check next activity D
5 >= 4
Activity selected because of satisfaction.
Check next activity E
3 >= 7
We can’t select this activity because that is not satisfied.
Check next activity F
5 >= 7
We can’t select this activity because that is not satisfied.
Check next activity G
6 >= 7
We can’t select this activity because that is not satisfied.
Check next activity H
8 >= 7
Activity selected because of satisfaction.
Check next activity I
8 >= 11
We can’t select this activity because that is not satisfied.
We checked every activity one by one and the selected activities are:
 Activity Start Time Finish Time A 1 4 D 5 7 H 8 11

Solution No. 2
 2
 5

 6
1
 1
 3
 7
2
 2
 4
3
 3
 5
 7
4
 1
 4
 6
 7
5
 1
 5
6
 2
 4
 5
7
(b)   Graph