Due Date: December $25$th$,2023$ until $23$:$59$

Question $1$: Consider the Differentiated Set Coverage Problem:

Input: $n$ items, $U=($:$1,2,$dots,$n$:$),$ coverage requirements of the items $f=($:$f_1,f_2,$dots,$f_n$:$),m$ sets, $S_1,S_2,$dots,$S_m,$ price of the sets $p=($:$p_1,p_2,$dots,$p_m$:$).$

Let $x=($:$x_1,x_2,$dots,$x_m$:$)$ be the selection decisions of the sets, $x_{i}in\{0,1\}.$

Output: A minimum price selection $x$ of the sets $S_1,S_2,$dots,$S_m$ that can cover the items in $U$ at least $f$ times.

Ex: Let $n=5$ and $U=($:$1,2,3,4,5$:$)$ having coverage requirements $f=($:$1,2,1,2,1$:$).$

Let $m=5$ and $S_1=\{1,2\},S_2=\{2,3,4\},S_3=\{2,5\},S_4=\{3,4\},S_5=\{1,4\}$ with prices $p=($:$5,6,10,2,4$:$).$

For instance, item $j=2$inU should be covered by at least $f_2=2$ different sets $S_i.$ We note that item $2$ can be covered by $S_1$ with price $p_1=5,$ by $S_2$ with price $p_2=6$ and by $S_3$ with price $p_3=10.$

Determine a greedy selection rule for the sets. Design a greedy algorithm for the Differentiated Set Coverage Problem and report the pseudocode.

Discuss the time complexity of your greedy algorithm. Is it efficient? Can your algorithm find the optimum solution?

Implement your algorithm in Python. Use the input given in the example and report the console outputs and your Python code scripts.