Question $2.(20$ marks$)$ A catering service receives $n$ orders, each requiring exactly one time unit to

complete. There is only one cook, so these orders must be completed one at a time; the cook starts work

at time $0.$

Order $i,1in,$ has a deadline $d_i($in time units$)$ by which it must be completed, and a profit

$p_i>0$ that the catering service receives if the order is completed by the deadline; if the order is completed

after the deadline there is no profit made and therefore it is not done at all. Note that several orders may

have the same deadline $($e$.$g$.,$ around lunch time$).$ The catering service must decide on a schedule in which

to do a subset of the orders, each completed by its deadline.

Describe an $O(n^2)$ greedy algorithm that takes as input the set of orders with their deadlines and profits

$J=\{(i,d_i,p_i)$:$1in\}$ and outputs a schedule of maximum profit. A schedule is a function $S$ that

maps each order $i$ to a time slot $j,$ where $j$ is a positive integer, meaning that order i will be done during

the time interval $(j-1,j)$; or to the time slot $+,$ meaning that order i will not be done. The schedule $S$

cannot map two different orders to the same time slot $($because there is only one cook who completes the

orders, one at a time$)$; and if it maps order $i$ to time slot $j0,$ then $j{d}_i($since every order that is

done must be finished by its deadline$).$ The profit of schedule $S$ is the sum of the orders that are done,

i$.$e$.,{\displaystyle \underset{1in}{\overset{?}{}}}$&$S(i)p_i.$

Prove that your algorithm is correct and analyze its running time. $($It can be done in $O(nlogn)$ time,

but $(n^2)$ is good enough for the purposes of this question.$)$

Hint. No job can be scheduled after the maximum deadline. What job should be scheduled in the slot

ending at that deadline?