1. The activity selection problem: There is only one machine. The profit of each job is 1 The goal is to maximize the profit. This is equivalent to finding the largest set of jobs that can be scheduled on one machine. Ordering by a non-decreasing order of the finish times produces an optimal solution (a) Show an input for which ordering by a non-decreasing order of the starting times does not produce an optimal solution. If you can, show that for an infinite values of n, there are inputs for which this greedy algorithm produces a solution whose profit is almost 1 of the optimal profit. b) Show an input for which ordering by length (from the shortest to the longest) does not produce an optimal solution. If you can, show that for infinite values of n, there are inputs for which this greedy algorithm produces a solution whose profit is almost half of the optimal profit