sql - 填充槽的算法

Question

我正在寻找一种算法来填充多个槽位，这些槽位已经填充到一定程度。

• 当前水平和可用填充数量是已知的
• 结果级别应尽可能相等，但不能降低现有级别
• 插槽从左到右填充，因此如果不可能达到相同级别，则左侧插槽会获得更高级别

Examples http://img695.imageshack.us/img695/6529/fill.png

上图展示了六个示例，每一列代表一个插槽。灰色区域已经填充，蓝色区域是新元素的预期位置。

---

我可以遍历我的插槽并将最低插槽的数量增加 1 直到可用数量被消耗，但我想知道如何实际计算新的填充水平。

我将使用 SQL/PL/SQL 来实现它，但也欢迎使用其他代码:)

Answer 1

这很简单。

除了某些情况*，您可以将其想象成倒水并让它充满。

1. 排序。您还可以使用优先级队列。
2. 跟踪当前最小列数。
3. 获取最小列和第二个最小列。
4. 用可用项目数或最多第二个最小列填充最小列。
5. 增加当前最小列的数量。
6. 转到第 4 步，直到所有列都处于同一级别，除非使用可用项目的数量，或增量(第二个最小值 - 第一个最小值)乘以当前最小列数。如果可用项的数量不够，只需做简单的数学运算(除法和余数)来填充列，然后用余数从左边开始填充。
7. 当所有列都处于同一水平时，使用第 6 步中描述的简单数学部分。

你应该很好。

此算法在 O( n log n ) 时间内运行。

*有些情况下这没有意义，但无论如何您仍然想这样做:

 #
 #
##
###
###

在那种情况下，您将填充第三列，然后是第一列，然后是第二列，但当然不是完全填充水。