在O(n)时间内重叠约会？

Question

我最近在接受采访时被问到这个问题.虽然我是上不来的Ø(ñ ²)的解决方案,面试官与一个痴迷Ø(ñ)解决方案.我还检查了其他几个我理解的O(n log n)解决方案,但是O(n)解决方案仍然不是我的一杯茶,它假定约会按开始时间排序.

有谁能解释一下？

问题陈述:您有n个约会.每个约会包含开始时间和结束时间.您必须有效地重新调整所有冲突的约会.

人:1,2,3,4,5
App开始:
2,4,29,10,22 App结束:5,7,34,11,36

答案:2x1 5x3

O(n log n)算法:单独的起点和终点如下:

2s,4s,29s,10s,22s,5e,7e,34e,11e,36e

然后对所有这些点进行排序(为简单起见,我们假设每个点都是唯一的):

2s,4s,5e,7e,10s,11e,22s,29s,34e,36e

如果我们连续开始没有结束那么它是重叠的:2s,4s相邻,所以重叠就在那里

我们将保持"s"的计数,并且每次遇到它时将+1,并且当遇到e时,我们将计数减少1.

Answer 1

在O(n)中不可能解决这个问题.

您至少需要按预约开始时间排序,这需要O(n log n).

如果列表已经排序,则有一个O(n)解决方案.该算法基本上涉及检查下一个约会是否与任何先前的约会重叠.这个有一点微妙,因为当你运行它时你实际上需要两个指向列表的指针:

• 正在检查当前的约会
• 到目前为止遇到的最新结束时间的约会(可能不是以前的约会)

如果您有其他约束,例如固定数量的约会时间段,则只能存在未分类情况的O(n)解决方案.如果是这种情况,那么您可以使用HashSets来确定哪个约会覆盖每个时间段,算法大致如下:

• 为每个时隙创建一个HashSet - O(1)因为时隙号是固定常量
• 对于每个约会,将其ID号存储在它所涵盖的插槽的HashSets中 - O(n),因为为每个约会更新一定数量的时隙是O(1)
• 运行插槽,检查重叠 - O(1)(或O(n)如果要迭代重叠约会以将它们作为结果返回)

Answer 2

假设您对开始和结束时间以及您进行调度的分辨率有一些限制，似乎很容易将每个约会变成它使用/不使用的时间的位图，然后执行使用中的槽上的计数排序（又名桶排序）。由于这两者都是线性的，因此结果应该是线性的（尽管如果我的想法正确，它应该与时间段数量而不是约会数量呈线性关系）。

至少如果我在面试中问这个问题，我希望候选人询问这些限制（即，是否允许这些限制）。考虑到将约会安排在 1000 年后的不切实际程度，或者安排到​​甚至一分钟（更不用说像纳秒之类的东西）的精确度，它们在我看来是合理的限制，但你应该在假设它们之前询问。