Problem $1.$ Your coding club is organizing a long hackathon in a computer lab and you

want to organize it in such a way that for every point during a time window $[t_0,t_{\text{e}\text{n}\text{d}}),$

at least one person is hacking in the lab.

Say you have $n$ coders $\{p_1,p_2,dots{p}_n\},$ and each person's availability to help out is

given by a continuous time interval, and that if they are going to code at all, they will

be coding for that entire interval. Formally, coder $p_i$ is available to help out in the time

interval $[s_i,f_i),$ and if they work at all, they will be in the lab from time $s_i$ to time $f_i,$

where iin$\{1,2,$dots,$n\}.$ Assume that you already know that you have enough volunteers

so that at each point in the time window $[t_0,t_{\text{e}\text{n}\text{d}})$ there is at least one person able to

code. You therefore decide to solve the following coder selection problem: choose a

minimum number of volunteer coders to participate in the hackathon, to ensure there

will always be at least one person in the lab during the whole time window $[t_0,t_{\text{e}\text{n}\text{d}}).$

a$)(10$ points$)$ Let $P_0$ be the set of coders that are able to code in a time window that

includes $t_0.$ Written formally, this means

$P_0=\{p_i$:$t_{0}in[s_i,f_i)\}$

Let $p^{**}in{P}_0$ be the person in this group with the latest finish time $f^{**}$ among all

members of $P_0.$ Prove that there exists an optimal solution to the coder selection

problem that uses $p^{**}$ as one of the coders.

b$)(10$ points$)$ Algorithm $1$ is pseudocode for a greedy procedure for choosing coders,

which takes in start times and finish times for the $n$ coders and the time window

that needs to be "covered". You can assume that for each time $t$ in $[t_0,t_{\text{e}\text{n}\text{d}}],$ there

is at least one coder whose shift "covers" that time $t.$

This code continuously updates $C,t,$ and $P_t.$ Explain what each of these represents.

Then prove whether this code will produce the optimal solution to the coder selection

problem.