#3 Activity Scheduling with Revenue(15 pts) Activity scheduling problem from the greedy algorithm class: Suppose that different activities earn different amounts of revenue. In addition to their start and finish times s, and f, each activity a,has revenue r, and our objective is now to maximize the total revenue: a,EA In class you found out that we can't use a greedy algorithm to maximize the revenue from activities, and we noted that dynamic programming will apply. Here you will develop the DP solution following the same steps as for the other problems (e.g., problem 3 above), but you are responsible for the details. Your analysis in (a) and (b) below should mirror that of section 16.1 of CLRS. (a) (3 pts) Describe the structure of an optimal solution A for S, as defined in CLRS, and use a cut and paste argument to show that the problem has optimal substructure. #3 Activity Scheduling with Revenue(15 pts) Activity scheduling problem from the greedy algorithm class: Suppose that different activities earn different amounts of revenue. In addition to their start and finish times s, and f, each activity a,has revenue r, and our objective is now to maximize the total revenue: a,EA In class you found out that we can't use a greedy algorithm to maximize the revenue from activities, and we noted that dynamic programming will apply. Here you will develop the DP solution following the same steps as for the other problems (e.g., problem 3 above), but you are responsible for the details. Your analysis in (a) and (b) below should mirror that of section 16.1 of CLRS. (a) (3 pts) Describe the structure of an optimal solution A for S, as defined in CLRS, and use a cut and paste argument to show that the problem has optimal substructure