Your friend at your job has a vendetta against the IT department and is devising a strategy to annoy them. He has obtained the on-call schedule S = [(s1, f1),(s2, f2), ...,(sn, fn)], where si and fi are the times at which employee i is scheduled to start and finish his or her on-call time. Every time your friend files an IT ticket, it will be sent to all on-call IT employees, annoying them. In other words a ticket filed at time t will annoy employee i if si t fi . Your friend wishes to file a minimal number of tickets that will annoy everybody in the IT department. For instance, if S = [(4, 12),(0, 8),(10, 14)], then filing tickets at times [0, 4, 13] or [3, 9, 10] are valid solutions that annoy everybody, and [8, 14] is an optimal solution.

(a) Devise a greedy algorithm to compute an optimal solution to the problem.

(b) After making your greedy choice, show that the problem is reduced to a smaller subproblem.

(c) Prove the greedy choice property by showing that there is an optimal solution that agrees with the first greedy choice your algorithm makes.

(d) Prove the problems optimal substructure by showing that the optimal solution to the subproblem (described in (b)) combined with the greedy choice leads to an optimal solution.