Please explain and show all necessary work.

3. (Intermediate) (20 points) Interval Selection Problem (ISP) a.k.a. Action Selection in Ch 16.1. In ISP, we are given n intervals (s1 fi), (a2, b2), (am, bm.), and are asked to find a largest subset of intervals that are mutually disjoint. See Ch 16.1. For simplicity, let's assume that all a, b values are distinct. We refer to a and bi as interval i's starting and ending times respectively. Also assume that intervals are ordered in increasing order of their ending times, i.e., b1 b2 bn. In class we learned that the greedy algorithm that repeatedly picks t interval i with the smallest ending time bi is optimal; of course, the newly chosen interval must be disjoint from the intervals we have chosen so far. In this problem, we want to prove the optimality of this greedy algorithm, which we call Earliest Ending (EE) (a) (0 point, just illustration) The greedy algorithm EE first chooses interval 1 since it has the earliest ending time. We claim that there exists an optimal solution that includes interval 1. Towards this end, consider an arbitrary optimal solution which consists of intervals ii, iz, ...,ij: as before, intervals are ordered in increasing order of their ending times. We observe that inte 1, i ...,iL are also mutually disjoint. This is because interval i ends before any of i ...2k starts, and interval 1 ends no later than interval i Hence we 21 obtained an optimal solution including interval 1, proving the desired claim. (b) (15 points) Extend the above argument: Let i2 be the second interval the greedy algo rithm ECE chose. Show that there is an optimal solution that includes intervals 1 and 22