Introduction to Algorithm 3rd edition

2. (Exercise 16.1-3) Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. For example, using the approach of selecting the activity with the earliest start time does not yield an optimal solution for the following set of activities, since it yields a subset of 1 activity (a,). when there exists a compatible subset of activities of size 2 (a, and a) Give an example to show that the approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work. (That is, create a set of activities, and show that for that set of activities there exists a subset of compatible activities larger than the subset generated by always picking the compatible activity of least duration) a. b. Do the same for the approach of always selecting the compatible activity that overlaps the fewest other remaining activities. In the case of a tie, you must explain why none of the tied options can result in an optimal solution. Hint: Start by making a few stacks of several activities with the same start and finish times, and then have exactly one activity that doesn't overlap them. Then make sure that activity isn't part of an optimal solution)