algorithm - 排序不同类型对象的高效算法

Question

鉴于我们有一组不同类型的视频(例如类型 A、B 和 C，...)，我们正在寻找一种有效的算法来将这些对象排序到播放列表中，以便我们具有最大的分散性。也就是说，如果可以避免的话，我们要确保来自 A 的两个视频不会背靠背放置。播放列表会重复播放(结束时重新开始。所以这方面也应该考虑)。

什么是能够以良好的色散执行上述操作的有效算法？

示例输入:

• A 类型的 5 个对象(A1、A2、A3、A4、A5)
• 3 个 B 类对象(B1、B2、B3)

输出 - 不是最优的

A1、B1、A2、B2、A3、B3、A4、A5

这不是最佳选择，因为在 A4 之后播放 A5，然后播放列表循环返回并播放 A1。现在我们已经从类型 A 连续播放了 3 个视频。

最佳输出

A1、B1、A2、A3、B2、A4、B4、A5

这是最佳选择，因为我们只有 2 个相同类型的视频连续播放。

请注意，该算法应该适用于不同数量的类型和视频。

Answer 1

这与我几年前遇到的一个问题类似:混合液体以避免分层。这个想法是，如果您将液体 A、B 和 C 混合到一个容器中，您不希望只是将它们一个接一个地倒入容器中。相反，您想按相对比例添加一些 A、一些 B、一些 C 等。

这与在列表中均匀分布项目的问题相同。

假设您有 30 个 A 类视频、20 个 B 类视频和 10 个 C 类视频，总共有 60 个视频。那么，每隔一个视频必须是 A。每三个视频是一个 B，每六个视频是一个 C。

所以 A 位于 0、2、4、6、8 等处。 B 位于 0、3、6、9、12 等处。 C 位于 0、6、12、18 等处。

显然，您必须解决冲突。

我这样做的方法是构建一个最小堆，其中包含视频类型及其频率，以及它的当前位置，从频率/2 开始。所以堆包含:{A,2,1},{B,3,1},{C,6,3}。

要生成您的列表，请从堆中移除最低的项目并将其添加到您的列表中。然后，把它的频率加到当前位置，放回堆上。所以在第一次通过后，你输出了 A，你的堆现在包含:{B,3,1},{A,2,2},{C,6,3} .

输出 B，然后将其加回去，得到 {A,2,2},{C,6,3},{B,3,4}

当然，您还需要保留每个项目的计数，每次输出该项目时都会递减，如果计数变为 0，则不会将其添加回堆中。

大约一年前，我在我的博客中详细介绍了这一点。参见 Evenly distributing items in a list .

就效率而言，该算法的复杂度为O(n log k)，其中n为视频总数，k为视频数量视频类型。