Activity Scheduling Problem: Consider nn activities $\{1,2,...,$ nn$\}$ with start times ss$1,...,$ ssnn and finish

times ff$1,...,$ ffnn$,$ that must use the same resource $($such as lectures in a lecture hall, or jobs on a

machine.$)$ At any time only one activity can be scheduled. Two activities ii and jj are compatible if

their time intervals $[$ssii$,$ ffii$]$ and $[$ssjj$,$ ffjj $]$ have non$-$overlapping interiors. Your objective is to determine

a set of compatible activities of maximum possible size. For each of the greedy strategies below,

determine whether or not it provides a correct solution to all instances of the problem. If your answer

is yes, state and prove a theorem establishing the correctness of the proposed strategy. If your answer

is no$,$ provide a counterexample $($i$.$e$.$ specific start and end times$)$ showing that the strategy can fail

to find an optimal solution.

a$.$ Order the activities by increasing total duration. Schedule activities with the shortest duration

first, satisfying the compatibility constraint. If there is a tie, choose the one that starts first.

b$.$ Order the activities by increasing start time. Schedule the activities with the earliest start times

first, satisfying the compatibility constraint. If there is a tie, choose the one having shortest

duration.

c$.$ Order the activities by increasing finish times. Schedule the activities with the earliest finish

times first, satisfying the compatibility constraint. If there is a tie, pick one arbitrarily.