设计一个一维停车场，可以停车两轮车(1个车位)、一辆车(2个车位)或一个公共汽车(4个车位)

Question

这个问题是对这个问题的扩展。我也是头脑风暴在这个问题声明，其中一个一维停车场有N个插槽将有不同大小的停车场要做。一辆两轮车占一个车位，一辆汽车占两个车位，一辆公共汽车占四个车位.

我们必须设计一个有效分配空间的系统。效率衡量标准是，我们应该能够容纳最大的车辆，并将它们分配到靠近入口的地方(假设时隙1最近于2，然后是3等等)。)

与上述邮件不同的是，我寻求关于我们可以使用什么样的算法来进行分配的建议。我们可以将这个问题与OS中发生的内存分配问题进行比较。这是可以考虑的，因为有许多不同大小的进程(1、2和4)需要在主内存(我们的停车场)中分配空间，如果是可变大小的内存分配，有3种算法：

 1. Best fit: allocate the most optimum space 
 2. Worst Fit: allocate the least optimum space
 3. First Fit: allocate the first available space 

最好的适应可能是一个很好的选择，但它有较高的时间开销。第一次适应是一个很好的选择，但它可能会造成空间的浪费。

还有其他算法/数据结构可以用于这样的分配吗？

Answer 1

你要在入口处附近安排车辆。我假设每辆车都很重要，所以与其分配4/1/1/1/ 1 /1/1/1/4的车辆，不如用1/1/1/1/4将四辆车移到前面，然后将一辆车向后移动。

我还假设车辆到了，你给他们安排一个车位，最后他们就离开了。一旦停车，车辆就不会被移动。

首先，你收集了一些统计数据--有多少两轮车、汽车和公共汽车通常会到达？然后，你为两轮车预留1-4k槽，为汽车预定4k+1到4l，为公共汽车预留4l+1到n，这样它们通常适合。

每辆车进入其所在区域的第一个可用位置。如果该区域已满，则移到前一个区域(S)。如果它们都装满了，你就把车移到下一个区域。为了简化事情，公共汽车只移动到插槽4j+1到4j+4的一些j，汽车移动到2j+1到2j+2的一些j。

这就确保了两轮车往往是第一位，然后是汽车，这使得成本最低。