algorithm - 在 O(n) 时间内找到重叠约会？

Question

我最近在一次采访中被问到这个问题。尽管我能够想出 O(n²) 解决方案，但面试官对 O(n) 解决方案。我还检查了一些我理解的 O(n logn) 的其他解决方案，但是 O(n) 解决方案仍然不是我的菜，它假定约会按开始时间排序。

谁能解释一下？

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

Person: 1,2, 3, 4, 5
App Start: 2, 4, 29, 10, 22
App End: 5, 7, 34, 11, 36

Answer: 2x1 5x3

O(n logn) 算法: 像这样分开起点和终点:

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)如果你想遍历重叠约会以将它们作为结果返回)