Question $1.(20$ marks$)$ A video production facility has $n$ videos to process. The processing of each

video $i,1in,$ is done in two phases. In the first phase, the facility's editor edits the video. After the

first phase of video $i$ is finished, the edited video is processed by computer. The first phase of video i takes

$f_{i}0$ units of time and the second phase takes $s_{i}0$ units of time.

The facility has a single video editor to do the first phase but it has $n$ computers to do the second

phase. So$,$ the first phase must be done sequentially by the single editor, while the second phase can be

done in parallel by the computers: As soon as the editor is finished editing a video, she feeds it into one

of the free computers for the second phase, even as other computers may still be processing the videos

whose first phase she completed earlier. The completion time of a video is the time by which its second

phase is finished. The manager of the facility wants to find a schedule that minimizes the maximum

completion time over all $n$ videos $-$ that is$,$ the earliest time by which both phases of all videos have

been been completed. $($This quantity is called the makespan of the schedule.$)$

Describe an efficient greedy algorithm that takes as input the set of videos and the length of their first

and second phases $V=\{(i,f_i,s_i)$:$1in\}$ and outputs an optimal schedule. In this case, a schedule

is simply a permutation of the integers from $1$ to $n,$ indicating the order in which the editor processes the

videos. This determines the time by which each video finishes, and therefore the maximum completion

time over all videos, which is the quantity we want to minimize.

Prove that your algorithm is correct and analyze its running time.