Problem 4. Bob is given n assignments to do, each with a length and a deadline. That is, assignment i corresponds to a length li and a deadline di (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 assignments), such that no assignment is completed more than k days after its deadline, if one exists. (Bob does not rest between assignments: he starts a new one as soon as the previous is done...)

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.

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:

a) Describe your algorithm in plain English.

b) Prove the correctness of your algorithm.

c) Analyze the time complexity of your algorithm.