Sit N people around a table so as to minimize the maximum difference in height between any two adjacent people

Question

(This is actually a coding challenge for an interview. Unfortunately, only 2 test cases are coded, so even if my solution passes them both, that doesn't tell me I've found the correct solution. Also, not knowing the correct solution, I can't write test cases myself.)

Here's one example for a possible set of $N = 4$ people. The heights could be $$ h = \{5, 10, 6, 8\} $$

A possible solution is sitting people such that the person tall 5 has person tall 6 immediately to their left, and person tall 8 immediately to their right; then person tall 10 would be opposite to person tall 5; the maximum difference in height is between person tall 6 and person tall 10, and it's equal to 4. A better solution cannot be found for such an example.

But what in the general case?

This is my reasoning.

• If the table was not circular, I could sit all people sorted from shortest to tallest, and that would minimize the maximum difference between any two adjacent people.
• But the table is circular, so such an arrangement doesn't work because the tallest and shortest persons can be beside each other (doing so would maximise the maximum difference), at least one person has to be between them, and possibly more.

At this stage of my reasoning I thought that the "round" table can be thought of like this:

         T (tallest person)
       +---+
       |   |
       |   |
some   |   | some
people |   | people
here   |   | here
       |   |
       |   |
       +---+
         S (shortest person)

• Whichever the arrangement is, the heights should increase when going from the shortest to the tallest person, whether we go clockwise (left side in the sketch above) or counterclockwise (right side in the sketch above).

I'm pretty sure about this last point, and I think it also guarantees that any solution strategy cannot be cheaper than the cheapest way to sort the whole list of people. As in, the cost of the optimal algorithm is at least the cost of the cheapest sorting algorithm.

• Therefore a strategy to the solution seems to consist in sorting people by height, sitting them like this

           T (h1, tallest person)
         +---+
      h2 |   |
      h3 |   |
         |   |
     ... |   | none here for now
         |   |
   h(n-2)|   |
   h(n-1)|   |
         +---+
           S (hn, shortest person)
  

  and then moving a selection of those on the left side to the right side without changing their relative order.

But how do I make the choice of which ones I should move to the other side?

Here I have the feeling that moving odd-numbered people (or, instead, even-numbered people) to the other side of the table gives a solution.

But I'm not sure.

Answer 1

Let the heights be $x_1\le x_2\le \dots\le x_n$.

I claim that for $n\ge 3$ the minimax difference is $$ \max_{i=2,\dots,n-1} |x_{i+1} - x_{i-1}| \tag{1} $$ with an optimal solution given by (where $r$ is the residue of $n$ modulo 2)

In view of the example, it suffices to show that for any seating the maximal difference is at least (1). Clearly we can assume that noone except $1$ and $n$ is seated next to people who either both higher or both lower, as otherwise we can reseat the people so that the maximal diffence does not increase.

Now let the maximum in (1) be obtained for $i^*$. If $i^*$ is not seated next to $i^*-1$, then the latter's higher neighbour should be $i^*+1$, and we are done; similarly, we are done if $i^*$ is not seated next to $i^* + 1$.

So let $i^*$'s neighbours be $i^*-1$ and $i^*+1$. Since the statement is obvious for $n=3$, I will assume that $n\ge 4$ and, without loss of generality, that $i^* \ge 3$. Clearly, the difference of heights between $i^*-2$ and her higher neighbour is at least (1), which finished the proof.