$4.$ A set X $=\{$x$1,$ x$2,...,$ xp$\}$ of exams needs to be scheduled by a university in a set R $=$

$\{$r$1,$ r$2,...,$ rq$\}$ of rooms. Each exam has a duration of one hour. The exam schedule must satisfy the following constraints:

$$ For each exam xi there is a set Ri $$ R of rooms that can be used for it$.$

$$ Exam xi must start no earlier than time si and no later than time ei$.$

$$ Each room ri can be used for only one exam at a time.

$$ Room ri is available only from time bi to time fi$.$

For example, consider the set of exams X $=\{$x$1,$ x$2,$ x$3,$ x$4,$ x$5\}$ and rooms R $=\{$r$1,$ r$2,$ r$3\}.$

$$ Room r$1$ is available between $2$ and $4,$ r$2$ is available between $3$ and $5,$ and r$3$ is available between $4$ and $5.$

$$ Exam x$1$ must start between $2$ and $4,$ exam x$2$ must start between $1$ and $5,$ exam x$3$ must start at $3,$ exam x$4$ must start between $3$ and $5,$ and exam x$5$ must start between $1$ and $4.$

$$ The sets of rooms where the exams can be administered are R$1=\{$r$1,$ r$2\},$ R$2=\{3\},$R$3=\{$r$1,$ r$3\},$ R$4=\{$r$2,$ r$3\},$ and R$5=\{$r$1,$ r$2,$ r$3\}.$

This is a solution: Schedule x$1$ in r$1$ at $2,$ x$2$ in r$3$ at $4,$ x$3$ in r$1$ at $3,$ x$4$ in r$2$ at $3,$ and x$5$ in r$2$ at $4.$

Question:

$$ Write an algorithm for solving this problem by reducing it to a maximum flow, minimum cut, or maximum matching problem. If there is a way of scheduling the exams the algorithm must return the value true, otherwise it must return the value false. Draw a figure illustrating how you model the problem using the example above.

$$ Prove that your algorithm correctly solves the above problem.

$$ Compute the worst case time complexity of your algorithm. If you need to compute a maximum flow, use the faster between the algorithms of Ford$-$Fulkerson and Edmonds$-$Karp.