What is the best reserved seat sorting algorithm?

Question

I am trying to find the best algorithm for the next sorting task.

The audience has strong> N = K × M places with one pass, K and M places in the aisle. It is assumed that K is larger than M , but I do not think it is very important. There are N people who are in bijection with seats (designated places). Assuming that people are not as expectation, what is the fastest way to build them in order to get them all in their places as quickly as possible?

I did some simple experiments (using random permutations), and it seemed like letting them line up randomly faster than having people in the front third (further down the aisle) line up first, then the middle third, then the third third. This seems to me wrong.

I write this in MatLab, if that matters at all. Any ideas or answers?

Answer 1

There is a very good article by Bakhmat, Berend, Sapir, Lysen and Stolyarov entitled Analysis of airplane landing through space-time geometry and random matrix theory , which models this exact problem for airplane landing. From their theses:

We show that the landing of the aircraft can be asymptotically simulated 2-dimensional Lorentzian geometry. The landing time is set to the maximum correct time between the curves in the model. The discrepancies between the model and the simulation results are closely related to the theory of random matrices. We then show how such models can be used to explain why some commonly used airlines have an ineffective and even detrimental internment policy.

Conclusions of the article:

• BEST: Window-middle passage
• AFTER THE OPTIMUM: Random boarding pass
• REALLY BAD: Back-to-Front

For your setup, I think this means that you should ignore how far down the aisle people are, and instead focus on how far away from the aisle . This model also takes into account the storage time of luggage, so you may have to adapt a little to your situation. In any case, I think this confirms what you find in your model.