Fake Hospital with Real Issues

The Great Fake Hospital $($TGFH$)$ wants its doctors to work over the holidays, but wants them

to have a choice in the matter. So$,$ they ask each doctor to let them know on which holidays

they are available to work.

For the next $n$ holidays, TGFH has determined the exact number of doctors they want on duty.

Thus, on holiday $i,$ they have a requirement that exactly $p_i$ doctors be present. Note that they

do not want more than $p_i$ or less than $p_i$ number of doctors, it must be exactly equal to $p_i.$ If

the number of doctors present is less than the requirement, they will have to turn away some

patients $($and lose money$).$ If the number of doctors present is more than the requirement,

they have to pay extra salaries!

TGFH has a total of $k$ doctors. Each doctor is asked to provide a list of holidays on which

they are willing to work. Thus, doctor $j$ provides a set $L_j$ of days on which they are willing

to work.

TGFH has collected all this information. But they don't know what to do with it$.$ Nobody on

their team ever took a course on Intro. Algorithms $$

So$,$ they ask you for help!!

You need to take these lists and try to return to each doctor $j$ a list $L_j^{\text{'}}$ with the following

properties:

$($A$)L_j^{\text{'}}$ is a subset of $L_j,$ so that doctor $j$ only works on days that they find acceptable.

$($B$)$ If we consider the whole set of lists $L_1^{\text{'}},L_2^{\text{'}},dots{L}_k^{\text{'}},$ it causes exactly $p_i$ doctors to be

present on day i for $i=1,2,$dotsn.

$($a$)$ Design a polynomial$-$time algorithm that implements this system.

$(5$ points$)$

Specifically, give a polynomial$-$time algorithm that takes the numbers $p_1,p_2,$dots,$p_n,$ and

the lists $L_1,L_2,$dots,$L_k,$ and does one of the following two things:

Return lists $L_1^{\text{'}},L_2^{\text{'}},$dots,$L_k^{\text{'}}$ satisfying conditions $($A$)$ and $($B$)$; or

Report $($correctly$)$ that there is no set of lists $L_1^{\text{'}},L_2^{\text{'}},$dots,$L_k^{\text{'}}$ that satisfy both proper$-$

ties $(A)$ and $(B).$