Consider the following problem: given a set of intervals S = {(a_1, b_1), ..., (a_n, b_n)}, find the largest subset of disjoint intervals. Two intervals (a_1, b_1) and (a_2, b_2) are disjoint if they do not overlap other than at their endpoints; in other words, if b_1 lessthanorequalto a_2 or b_2 lessthanorequalto a_1. For example, if S = {(1, 5), (3, 6), (5, 7)}, then the largest subset of disjoint intervals is {(1, 5), (5, 7)}. While brainstorming, you and your friends come up with four greedy strategies for this problem. For each strategy, prove or disprove that it always produces an optimal solution. Assume that ties are broken arbitrarily. Pick the shortest interval (minimum b - a). Remove all intervals that overlap this interval. Repeat. Pick the interval with the minimum start (a-value). Remove all intervals that overlap this interval. Repeat. Pick the interval with the minimum end (b-value). Remove all intervals that overlap this interval. Repeat. Pick the interval that overlaps the fewest other intervals. Remove all intervals that overlap this interval. Repeat. Select one of the above strategies for which you were able to prove that it always produces an optimal solution. Give a greedy algorithm for this problem, based on your selected strategy. Analyze the running time of your algorithm