Interval Selection Problem (ISP) a k a. Action Selection in Ch 16.1 In ISP, we are given n intervals (s_1, f_1), (a_2, b_2), ....., (a_n, b_n), 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_i and b_i as interval i's starting and ending times, respectively. Also assume that intervals are ordered in increasing order of their ending times, i.e., b_1 lessthanorequalto b_2 lessthanorequalto ... lessthanorequalto b_n In class we learned that the greedy algorithm that repeatedly picks the interval i with the smallest ending time b_i 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) 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 i*_1, i*_2, ..., i*_k; as before, intervals are ordered in increasing order of their ending times. We observe that intervals 1, i*_2, ..., i*_k are also mutually disjoint. This is because interval i*_1 ends before any of i*_1, ..., i*_k starts, and interval 1 ends no later than interval i*_1. Hence we obtained an optimal solution including interval 1, proving the desired claim. (b) Extend the above argument: Let i_2 be the second interval the greedy algorithm EE chose. Show that there is an optimal solution that includes intervals 1 and i_2. (c) just showing how the proof should be completed) This argument can be easily extended to show that for any k', there is an optimal solution that includes the first k' intervals that the greedy algorithm EE chose. This is proven by induction on k'. This proves the optimality of EE. (d) Not all greedy algorithms work. For example, we can repeatedly add the shortest interval that is disjoint from the intervals we have chosen so far. Show an example for which this algorithm fails to give an optimal solution. Interval Selection Problem (ISP) a k a. Action Selection in Ch 16.1 In ISP, we are given n intervals (s_1, f_1), (a_2, b_2), ....., (a_n, b_n), 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_i and b_i as interval i's starting and ending times, respectively. Also assume that intervals are ordered in increasing order of their ending times, i.e., b_1 lessthanorequalto b_2 lessthanorequalto ... lessthanorequalto b_n In class we learned that the greedy algorithm that repeatedly picks the interval i with the smallest ending time b_i 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) 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 i*_1, i*_2, ..., i*_k; as before, intervals are ordered in increasing order of their ending times. We observe that intervals 1, i*_2, ..., i*_k are also mutually disjoint. This is because interval i*_1 ends before any of i*_1, ..., i*_k starts, and interval 1 ends no later than interval i*_1. Hence we obtained an optimal solution including interval 1, proving the desired claim. (b) Extend the above argument: Let i_2 be the second interval the greedy algorithm EE chose. Show that there is an optimal solution that includes intervals 1 and i_2. (c) just showing how the proof should be completed) This argument can be easily extended to show that for any k', there is an optimal solution that includes the first k' intervals that the greedy algorithm EE chose. This is proven by induction on k'. This proves the optimality of EE. (d) Not all greedy algorithms work. For example, we can repeatedly add the shortest interval that is disjoint from the intervals we have chosen so far. Show an example for which this algorithm fails to give an optimal solution