7. [10 marks] Three people are working in a workshop. There are n jobs. Each job will take one hour of work by one person to complete. Job i has deadline di, where 1din. If job i is completed before di, it will generate pi dollars of profit. If it is completed after di, it generates no profit. We want to choose some jobs to assign to timeslots of the three workers so that the total profit is maximized. [3] (a) A greedy algorithm can solve this problem by looking at the jobs one by one (in some order) and deciding what to do with each one. Give such an algorithm. [3] (b) After your algorithm has looked at i jobs, it has constructed a partial solution Qi. Define Qi and Q as mathematical objects and define, formally, what it means for an optimal solution Q to extend Qi. [4] (c) Let 1in. Assume there is an optimal solution Q that extends Qi1. Show that there is an optimal solution Q^ that extends Qi, in the case where job i is done at the same time in Qi and Q, but by different workers. 8. [1 mark +5 bonus marks] There is a large city on an island. The Easter Bunny has left 100 Easter eggs at various intersections in the city. Assume you have no map of the city (and no paper on which to draw one). However, you have a big bag full of flat pebbles which you can leave at places in the city as markers. Each pebble has an arrow painted on one side. Assume you have enough pebbles so that you could leave one at every intersection in the city, plus one extra pebble to mark your starting point