问题：有 N 个人和 S 个插槽。每个人都有一个他正在忙的插槽列表。我们必须找到一个算法来找到一个所有这些都是免费的插槽。
我已经知道一个复杂度为 O(NS) 的算法。需要更好的算法。
您可以自由地动态维护不同的数据结构（无论何时安排会议，它们都会更新），这些数据结构可用于最终找到一个空闲位置。
问问题
303 次
4 回答
2
为每个插槽保留一个插槽计数器。为每个繁忙的插槽添加一个到该插槽插槽计数器；为所有人忙碌的插槽。
任何在考虑了所有人的繁忙时段之后仍然为零的槽计数器是所有人空闲的槽的计数器。可能是 O(k) 算法。
您可以设置一个位掩码/位集，而不是计数，其中人 N 的位掩码在他们忙碌的所有位置都设置了位 S。所有人的位掩码的按位或将具有对应于所有空闲槽的零位。
更新：您陈述问题的方式，您不必跟踪人员，只需保留一系列插槽占用指标。最初都标记为免费；当您浏览每个人的忙碌时段时，将相应的占用指示器标记为忙碌。完成后，任何仍然可用的数组指标都是您的答案。
于 2012-08-15T18:57:27.520 回答
0
生成一个大小为 S 的位掩码，其中设置了 S 忙时的位。按位或所有位掩码一起，然后提取未设置的位。
于 2012-08-15T20:37:22.733 回答
0
编辑：假设我们对每个人都有一个排序的插槽列表，算法将起作用
- 现在您有 N 个大小为 S（最大）的列表。合并排序此列表：http ://en.wikipedia.org/wiki/Merge_algorithm
- 典型的合并排序（使用堆）将导致复杂度 NlogK，其中 N 是所有“K”列表中元素的总数。但是，如果您的版本，N 列表中的每个元素都限制在 0 和 s-1 之间。因此，复杂度也受 S*log(N) 的限制。以最大“N”的堆大小迭代 N 列表，以 S 迭代为界。说得通？
因此，整体复杂度 = N*log(S) + S*log(N)
这是假设原始列表已排序，否则复杂度会上升到 N(SlogS)
于 2012-08-15T19:04:20.720 回答
-1
请记住，很可能没有解决方案，匈牙利算法将提供最接近的答案
于 2012-08-15T20:32:43.373 回答