Problem $5$ New team members are joining the Hokies, and there is a reassignment going on in the locker

room. A team member is assigned a single locker. Each locker is numbered $($both positive and negative$),$

and when someone moves the contents of a locker to any other locker, the moving time is proportional

to the distance between the lockers. If the contents of locker i are moved to locker j$,$ it takes $|$j $$ i$|$

hours. For example, to move contents of locker $5$ to locker $3,$ it takes $2$ hours. To move the contents

of locker $2$ to $6$ takes $4$ hours.

As a CS$4104$ student, the facility manager has asked you to design an algorithm that, given current

positions of members who need to be $($re$)$assigned and a proposed locker position, can assign lockers

with the aim of minimizing the time it takes for the last person to move. Below are example inputs

and expected outputs:

$$ Instance $1$:

Current assignments $($C$)$: $[4,-4,2]$

Available lockers $($A$)$: $[4,0,5]$

Output: $4$

$$ Instance $2$:

Current assignments $($C$)$: $[-10,-79,-79,67,93,-85,-28,-94]$

Available lockers $($A$)$: $[-2,9,69,25,-31,23,50,78]$

Output: $102$

Your task is to

$1.(15$ Points$)$ Design an efficient algorithm and provide the pseudo$-$code. $($Hint: The brute force

approach is to check all permutations and find the one that has the lowest time for the last person$)$

$2.(5$ Points$)$ Prove the correctness of the algorithm

$3.(5)$ Calculate the time complexity