Consider the schedule procedure of the scheduling algorithm with deadlines $($Algorithm $4\mathrm{.}4).$ Let d be the maximum deadline among the $7$ tasks. Modify the algorithm to schedule the tasks as late as possible without exceeding their deadlines.

First, initialize disjoint sets for integers from $0$ to d$+1.$ Let Small$($S$)$ represent the smallest member in the set S$.$ When scheduling a task, find the set S that includes the smallest deadline and the task itself. If Small$($S$)=0,$ remove the task. Otherwise, schedule the task at time Small$($S$)$ and combine sets S and the set that includes Small$($S$)-1.$

Assuming the use of the disjoint set data structure described in Appendix C$,$ show that this algorithm has a time complexity of O$($mlgm$),$ where m is the minimum of d and n$.$

$($Agorithm $4\mathrm{.}4)$ void schedule$($int n$,$ constint deadline$|],$eqsuence$\_$of $\_$integer& J$)$

$\{$

index i;

sequence$\_$of$\_$integer ;K

J $=[1]$ ;

for $($i$=2$; i $<=$ n$,$ i$++)\{$

K $=$ J and add i in increasing order of deadline$[$i$]$;

if $($K is feasible$)$

J $=$ K;

$\}$

$\}$