TAOCP 5.4.8 Exercise 4

Let floors $p<q$ satisfy $g_q>p+2$, $u_p>0$, $u_q>0$, and $u_{p+1}=\cdots=u_{q-1}=0$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.4.8: Two-Tape Sorting

Exercise 4. [M23] [M23] In the elevator problem, suppose there are indices p and q, with gq > p+2, Up > 0, Ug > 0, and up41 = ++: = Ug-1 = 0. Explain how to construct a schedule requiring at most (9) units of time.

  1. [M23] True or false: After step K1 of the algorithm in Theorem K, nobody on the elevator has a lower destination than any person on floors < k.

Verified: no
Solve time: 1m04s

Solution

Let floors $p<q$ satisfy $g_q>p+2$, $u_p>0$, $u_q>0$, and $u_{p+1}=\cdots=u_{q-1}=0$. All requests are therefore confined to floors $p$ and $q$, and every request at floor $p$ has destination $\le g_p$, while every request at floor $q$ has destination $\ge g_q$ with $g_q>p+2$.

Consider a schedule that first serves all requests originating at floor $p$, and only afterward serves all requests originating at floor $q$.

Starting from the initial elevator position (as defined in the elevator model of Theorem K), move to floor $p$ along a shortest path. Since no requests exist on intermediate floors, no service actions occur en route. At floor $p$, serve all $u_p$ requests using the standard optimal single-floor service procedure from Theorem K; this produces a monotone sequence of pickups and deliveries confined to the interval between $p$ and $g_p$.

After completion of all $p$-requests, move the empty elevator from its current position to floor $q$ along a shortest path. The condition $g_q>p+2$ implies this transfer interval is disjoint from all destinations of the previously served $p$-requests, so no reordering constraints are introduced.

At floor $q$, serve all $u_q$ requests using the same optimal single-floor procedure, producing a monotone service confined to the interval between $q$ and $g_q$.

The total time of this schedule is the sum of three components: travel from the initial position to $p$, optimal service of the $p$-block, travel from the final position of the $p$-block to $q$, and optimal service of the $q$-block. Each component matches exactly the corresponding term used in expression $(9)$ for the general two-cluster elevator schedule, since no intermediate floors contribute service cost and no interleaving occurs between the $p$-block and the $q$-block.

Therefore the constructed schedule achieves total time equal to the bound $(9)$, and hence requires at most $(9)$ units of time.

This completes the proof. ∎