The input is a set of jobs j1, j2, . . . , jN, each of which takes a one-time unit to complete. Each job ji earns di dollars if it is completed by the time limit ti, but no money if completed after the time limit.
a. Give an O(N2) greedy algorithm to solve the problem.
b. Modify your algorithm to obtain an O(N logN) time-bound. (Hint: The time-bound is due entirely to sort the jobs by money. The rest of the algorithm can be implemented, using the disjoint set data structure, in o(N logN).)