arrays - 安排N个人的 session

Question

问题:有N个人，S槽。每个人都有一个他忙的槽列表。我们必须找到一个算法来找到一个插槽，其中所有这些都是免费的。

我已经知道一个复杂度为 O(NS) 的算法。需要更好的算法。

您可以自由地动态维护不同的数据结构(它们将在安排 session 时更新)，可用于最终找到空闲时间。

Answer 1

为每个插槽保留一个插槽计数器。为每个人忙的插槽添加一个到该插槽 slotcounter；为所有人忙碌的时段。

任何在考虑了所有人的忙碌时隙后仍为零的时隙计数器是所有人空闲时隙的计数器。可能是一个 O(k) 算法。

您可以设置一个位掩码/位集，而不是计数，其中 N 的位掩码在他们忙碌的所有位置都设置了位 S。所有人的位掩码的按位或将具有对应于所有空闲槽的零位。

更新:按照您陈述问题的方式，您不必跟踪人员，只需保留一系列插槽占用指标即可。最初所有标记为免费；当您通过每个人的忙碌时段时，将相应的占用指示器标记​​为忙碌。完成后，任何仍然可用的数组指标就是您的答案。