3. Activity Scheduling Problem: Consider n activities {1, 2, ..., n} with start times S1, ..., Sn and finish times f1, ..., fn, 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 i and j are compatible if their time intervals [si, fi] and [si, f;] 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