$(10$ points$)$ Activity$-$Selection Problems

Consider a modification to the activity$-$selection problem in which each activity ai has, in

addition to a start and finish time, a value vi$.$ The objective is no longer to maximize the

number of activities scheduled, but instead to maximize the total value of the activities

scheduled. That is$,$ we wish to choose a set A of compatible activities such that P

ak in A vk

is maximized. Give an algorithm and a solution for the problem below.

Task Start Finish Value

$1143$

$2353$

$3065$

$4574$

$5395$

$6594$

$76103$

$88113$

$98125$

$1021411$

$1112166$