Suppose that your significant other has a list of n "sp which you are expected to treat him/her to dinner Each special day s has associated with it: e a: the actual date. You should buy the dinner on or a . di: the deadline. You MUST buy your partner din? otherwise you will suffer the unspeakable consequence d are distinct. One dinner can credit up to k special days. For insta February 10 with a deadline of February 24, and another s deadline of February 18, you can buy your partner dinner these special dates. 8. (5 points) Given a list S of special days and a number k that minimises the number of dinners that you must treat very busy with your studies and cannot afford to take mar output should be a set of days on which you go out for din? b) Give a moderately-sized (n- 8, k- 3) instance, showing the dates where your greedy solution schedules the dinners, and some alternate optimal (not necessarily greedy) solution also scheduling a minimal number of dinners. A diagram may be helpful in illustrating your instance and solutions. c) Give a proof that your greedy approach produces an optimal solution. You may nd it helpful to attempt a sequence of exchanges to transform an arbitrary optimal solution into your greedy solution without loss of optimality