Bob is given n assignments to do, each with a length and a deadline. That is, assignment i corresponds to a length , and a deadline d; (both positive integers; you can assume all deadlines are distinct). But Bob doesn't multitask well, and must do his assignments one after the other: he cannot start an assignment unless he's done with the one he was working on before (and, of course, cannot start earlier than day 1). Unfortunately, if any of the assignments is completed more than k days after its deadline, Bob gets 0 on that assignment which he wants to avoid! So he needs to come up with an ordering of the assignments (i.e., in which order to do the n assign- ments), such that no assignment is completed more than k days after its deadline, it one exists. (Bob does not rest between assignments: he starts a new one as soon as the previous is done...) Example: If the assignments are (,d) = (2,6), (l2, d2) = (4,4), and (3, d3) = (3,10) (so, n = 3) and k = 1, then a feasible schedule exists and could be (2,1,3), since starting with A2 on day 1 means finishing on day 1+ = 5 d + k, then starting A1 on day 5 means finishing on day 5+ 1 = 7 d+k, and starting A3 on day 7 means finishing on day 7+ 3 = 10 11=d3 +k. Day 1 (start) 4 days A2, due on Day 4 2 days A1, due Day 6 Day 5 Day 7 3 days A3, due Day 10 Day 10 Note that if in the above example we change k to 0, there would no longer exist a feasible ordering, as A2 cannot be completed before its deadline plus k = 0 days. a) Describe your algorithm in plain English. b) Prove the correctness of your algorithm. c) Analyze the time complexity of your algorithm. Your task is to give an algorithm for this problem that runs in O(n logn) time (i.e., its running time does not depend on k) and returns such an ordering, if it exists. If no ordering exists, you should report that as well. Remember to: