最好的预留座位排序算法是什么？
我正在尝试为以下排序问题找到最佳算法。
礼堂内有 N = K × M 个座位，沿一条过道，K 排，每过道有 M 个座位。假设 K 比 M 大，但我认为这不是很重要。有 N 个人在 与席位（分配的席位）的双射。假设人们不 比如等待，什么是最快的方式让他们排队以获取所有东西 尽快坐在座位上？
我进行了一些简单的实验（使用随机排列），它 似乎让它们随机排列比让它们更快 前三分之一（过道下方）的人先排队，然后 中间三分之一，然后是后三分之一。这对我来说似乎是错误的。
如果这很重要的话，我正在用 MatLab 写这篇文章。有什么想法或答案吗？
I'm trying to find the best algorithm for the following sorting problem.
There are N = K × M seats in an auditorium with one aisle, K rows, and M seats per aisle. The assumption is made that K is a bigger than M, but I don't think that's very important. There are N people that are in
bijection with the seats (assigned seats). Assuming that people don't
like waiting, what's the fastest way to line them up to get them all
in their seats as quickly as possible?
I ran some simple experiements (using random permutations) and it
seemed that letting them line up randomly is faster than having the
people in the front third (further down the aisle) line up first, then
the middle third, then the back third. That seems wrong to me.
I'm writing this in MatLab if that matters at all. Any ideas or answers?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Bachmat、Berend、Sapir、Skiena 和 Stolyarov 发表了一篇非常好的文章，题为 通过时空分析飞机登机几何和随机矩阵理论模拟了飞机登机的确切问题。从他们的摘要来看：
该论文的结论是：
对于您的设置，我认为这意味着您应该忽略过道有多远 人们，而不是关注他们离过道有多远。该模型还考虑了存放行李的时间，因此您可能需要根据您的情况进行一些调整。无论如何，我认为这证实了您通过模型发现的内容。
There is a very nice article by Bachmat, Berend, Sapir, Skiena and Stolyarov entitled Analysis of airplane boarding via space-time geometry and random matrix theory that models this exact problem for airplane boarding. From their abstract:
The conclusions of the paper are:
For your set-up, I think this means you should ignore how far down the aisle the people are and instead focus on how far from the aisle they are. This model also accounts for time to store luggage, so you may need to adjust that somewhat for your situation. In any event, I think this confirms what you are finding through your model.