Here instead of greedy algorithm, we will solve the activity selection problem via dynamic programming. However, in this case, we want to minimize the wasted time, i.e., we do not want to wait between activities, and want to start the next one right away. Hence, this is little different than the one we studied in the class.

(a) Define your sub-problem and state how dynamic programming can be used.

(b) Develop an algorithm for your sub-problem.

(c) Provide the pseudo-code and determine its complexity.

(d) Implement your approach and show that your algorithm works.