Problem $9-2$

You live in a country with very high medical costs and anticipate undergoing a super$-$expensive medical treatment for the time period $[S,F).$ Luckily, as long as you have at least one job, you will have a cheap health insurance which will fully cover your expensive treatment. You are also

very smart, so you get $n$ job offers, where the $i-$th job is for the period $[s_i,f_i),$ so that the union

of $[s_i,f_i)$ fully covers the desired interval $[S,F).$ For simplicity, assume the jobs are already sorted

by their starting times, so that $s_1{s}_2$dots$s_n.$

Of course, one possible solution is to take all the jobs $($it$\text{'}$s OK to have multiple jobs at the same

time$).$ However, being a naturally lazy person, you would like to take the smallest number of jobs which would cover the desired interval $[S,F).$

$($a$)(5$ points$)$ Design an efficient $O(n)$ greedy algorithm for this problem. For partial credit, give $O(n^2)$ algorithm. $($You will prove correctness in the next part.$)$

$($b$)(5$ points$)$ Prove the correctness of your algorithm using a local$-$swap argument.

$($c$)(4$ points$)$ Assume you can hold at most two jobs at the same time $($e$.$g$.,$ each job only has a day shift and a night shift, and you have to be at the job$).$ Does your solution from part $($a$)$ still work in this case? If yes, prove it$.$ Else, give a counter$-$example.