$2$ Securing the companies

$(10$ marks, including $2$ marks for documentation$)$

Assume that you are the manager of a security company tasked with assigning security officers

$($n$)$ to a group of companies $($m$)$ in a certain month with $30$ days numbered D$0,$ D$1,...,$ D$29.$ Assume

that security officers are denoted by SO$0,$ SO$1,...$ SOn$1$ and the companies are represented

by C$0,$ C$1,...$ Cm$1.$ There are three $8-$hour shifts per day: S$0($midnight$-8$am$),$ S$1(8$am$-4$pm$),$

and S$2(4$pm$-$midnight$).$ For each pair company$/$shift $($Cj $,$ Sk$),$ the company Cj has a different

number of security officers required for the shift Sk$,$ however, this is constant for each day of

the month.

The security officers specify the shifts they are interested in working on$,$ and they have the

opportunity to indicate more than one $(1)$ preferred shift. However, they cannot be allocated

to more than one $(1)$ shift per day. Further, the shift preference of each security officer should

be the same for all the days of the month $($and therefore specified only once per security officer$).$

Your task is to provide a plan for assigning officers to the companies for the coming month

according to the requirement of the number of security officers per shift by each company. For

each day of the month, and for each shift, each company should be allocated exactly the same

number of security officers it requests. There are $2$ integer parameters, $0<=$min$\_$shifts$<=30$

$($minimum number of shifts$)$ and $0<=$max$\_$shifts $<=30($maximum number of shifts$),$ and the

total number of shifts allocated to each security officer in a month should be within these two

integer parameters $($closed interval$).$

As long as you comply with the constraints above, you are free to allocate the security officers

any way you want.

The input to your function allocate consists of a list of preferred shifts provided by each

security officer and the number of security officers requested by the companies for each shift:

preferences is a list of lists, where preferences$[$i$][$k$],$ is a binary value $(0$ or $1),$ indicating

whether security officer SOi is interested in working on shift Sk in that month $(1$ indicates that

the officer is interested$).$ officers$\_$per$\_$org is a list of lists, where officers$\_$per$\_$org$[$j$][$k$]$

is a non$-$negative number that specifies how many security officers company Cj needs for shift

Sk on each day of that month.

Your task is to implement a function allocate$($preferences$,$ officers$\_$per$\_$org, min$\_$shifts,

max$\_$shifts$)$ which returns:

$$ None $($i$.$e$.,$ Python NoneType$),$ if no allocation satisfying all constraints exists.

$$ Otherwise, it returns a list of lists allocation, where allocation$[$i$][$j$][$d$][$k$]$ is equal

to $1$ if security officer SOi is allocated to work for company Cj during shift Sk on day Dd$.$

Complexity requirement: The worst$-$case time complexity of your solution should be

O$($m $$ n $$ n$).$