Well I have a problem with a Christmas assignment and my teacher is not responding(maybe he is skiing somewhere now) so I will need some help.
The algorithm is about an office and the waiting time of the customers. We have one office that has to serve $n$ customers $a_1, a_2,\cdots ,a_n$. We assume that serving time $t(a_j)$ for each customer $a_j$ is known. Let $a_j$ to be served after $k$ customers $a_{i_{1}},a_{i_{2}},\cdots ,a_{i_{k}}$. His waiting time $T(a_j)$ is equal to
$$T(a_j) = t(a_{i_{1}})+t(a_{i_{2}})+\cdots +t(a_{i_{k}})+t(a_{j})$$
I want to an efficient algorithm that will compute the best way to serve in order to reduce the total waiting time.
$$\sum_{j=1}^nT(a_j)$$
My first thought is that the customers with the smallest serving time have to go first and the obvious solution is apply a sorting algorithm.
Am I wrong?
Yes, serving the customers in ascending order of serving time is optimal.
To prove this, note that, if the customers are served in the order $a_{i_1}, a_{i_2}, \dotsc, a_{i_n}$ and if $t(a_{i_j}) > t(a_{i_{j+1}})$ for any $1 \le j < n$, then swapping the order of the customers $a_{i_j}$ and $a_{i_{j+1}}$ reduces the total waiting time by $t(a_{i_j}) - t(a_{i_{j+1}}) > 0$ time units.