$2.(50$ marks$)$ Consider a set of $\backslash ($ n $\backslash )$ jobs where each job $\backslash ($ i $\backslash )$ has a size, denoted by $\backslash ($ s$\_\{$i$\}\backslash ),$ and a target time, denoted by $\backslash ($ t$\_\{$i$\}\backslash ).$ There is a single resource and all jobs must be scheduled. Ideally, each job should be processed$/$completed before their target time has elapsed. However, this may not be possible, that is$,$ some jobs may finish processing after their corresponding target time has passed. The time between a job's target time and its completion time is referred to as its lag time, denoted by $\backslash (\backslash$ell$\_\{$i$\}\backslash ).$ If a job completes before its target time is reached, it has a lag time of $0.$ Your goal is to schedule the jobs such that the maximum lag time is minimized.

One potential greedy algorithm is to schedule the jobs based of Earliest Target Time First, i$.$e$.$ the returned schedule is a list of the jobs sorted by nondecreasing target times. Prove this algorithm completing the proof of the theorem below.

Theorem: $\backslash (\backslash$forall i $\backslash$exists $\backslash )$ an optimal schedule $\backslash ($ A$^\{*\}\backslash )$ which agrees with the partial greedy solution $\backslash ($ A$\_\{$i$\}^\{$G$\}\backslash ).$

Agrees: $\backslash ($ A$^\{*\}\backslash )$ agrees with $\backslash ($ A$\_\{$i$\}^\{$G$\}\backslash )$ iff the a sublist of the first $\backslash ($ i $\backslash )$ elements of $\backslash ($ A$^\{*\}\backslash )$ equals $\backslash ($ A$\_\{$i$\}^\{$G$\}\backslash ),$ i$.$e$.\backslash ($ A$^\{*\}[$: i$]=$A$^\{$G$\}[$: i$]\backslash )$

Proof by induction:

You take it from here. State the three steps for the inductive proof. In the third step consider the greedy algorithm's choice for the ith job to be scheduled. How does this compare with the choice of $\backslash ($ A$^\{*\}\backslash )?$ What cases could potentially arise? Handle each case in some way, show the theorem will still hold, it's a contradiction, it's trivial, etc. Your arguments should be mathematical in nature, stating things like "clearly the lag time does no worse here" with no formal justification is not good enough.