3. Consider the activity selection problem as discussed in class where we are given n intervals (x1,y1),..., (n, yn) and we would like to select a maximum number of pairwise disjoint intervals. Consider the following greedy algorithm for this problem: Algorithm 1 Activity Selection((1: Y1)...., (In, Yn)) A = {1,...,n} S+0 while A + 0 do Pick i A that minimizes |{j EA | (xi, yi) (xj, yj) 0}| breaking ties arbitrarily interval has smallest number of intersections i-th S+SU{i} A+ A- {i} AA end while return(S) {jA | (xi, yi)(xj, yj) 0} Removes i and all its intersecting intervals from A Prove or disprove that this greedy algorithm always outputs the optimal answer. To disprove you would need to provide a counter-example. To prove you need to prove that for all possible inputs it provides the optimal answer.