Homework 20
due Fri 4/5 in class

For the following problem, develop a greedy algorithm to solve the problem using the 15.5 step greedy algorithm development template. Give each of the steps; don't just give an algorithm — the point here is understanding the process and being able to apply it.

1. Print Services has n jobs to complete, and each job i has a length t_i and a deadline d_i. A feasible schedule is one in which all of the jobs get done before their respective deadlines. Find a feasible schedule if one exists.

   (Note: While this isn't an optimization problem as such, there is an optimization version which, if solved, addresses the original problem. Solve the problem that way: Develop a greedy algorithm to find a schedule which minimizes the amount by which the most-late job misses its deadline. Then explain how finding such a schedule allows you to solve the original problem.)