logo标签列表

检查数组之间重叠的算法。

arraysalgorithmsorting
3
我有两个数组，一个是已存在约会的数组，另一个是潜在约会的数组。每个数组都包含现有或潜在约会的起始和结束时间值。每个数组中的约会已按照起始时间排序。
我需要检查每个潜在约会是否与每个现有约会有重叠。虽然我可以每次从现有约会的开头开始检查，但我正在寻找更高效的方法。
用哪种编程语言？ - Mark C.
4个回答
1
这可以在O（nlogn）的时间内高效完成。考虑两个数组A和B，分别包含现有和潜在的约会。按照约会结束时间（A_end）和开始时间（A_start）递增的顺序对A进行排序。这需要O（nlogn）的时间。
对于B中的每个潜在约会： s = 分配的起点 t = 分配的终点
现在，在A_start和A_end数组上进行二进制搜索，以查找所有在s-t之间的约会，这需要o（logn）的时间。 [ #重叠= （结束时间<= t的预约） - （结束时间< s的预约） + （结束时间> t的预约） - （开始时间> t的预约） + ]
因此，总体顺序为O（nlogn）。 编辑：#overlaps = sum_1 + sum_2
这里，sum_1代表那些结束时间<=t的区间。但是为了仅查找重叠的区间，我们必须减去那些结束时间<s的区间。因此，我们只得到那些结束时间>=s且<=t的区间。
这里，sum_2代表那些结束时间>t的区间。但是为了仅查找重叠的区间，我们必须减去那些结束时间>t的区间。因此，我们只得到那些结束时间>t但开始时间<=t的区间。
可以通过以下事实证明任何重叠的区间要么具有结束时间<=t，要么具有结束时间>t。因此，它将位于sum_1或sum_2中。
不正确，因为您不能以这种方式使用二分查找。数组A仅按endtime排序，开始时间可以是任何顺序。假设A中的所有间隔都在s之后结束，但只有最后一个间隔在t之前开始。然后，您需要检查A的所有元素以查找重叠的间隔。 - BKE
1
@BKE请查看编辑部分。我认为我们不必找到实际的重叠，因为它可能需要O(n^2)以上的时间，因为所有区间都可能重叠。这个算法只是用来计算#重叠数。 - Rishit Sanmukhani
1
现在通过开始时间和结束时间排序都是正确的。请注意，您无需计算（结束时间<= t的约会）, 因为前两项的总和就是约会数量。因此，您只需要计算非重叠间隔并从数组长度中减去它，就可以省去一次二分搜索了。 - BKE
1
这个想法是：开始比较第一个间隔与其他间隔。如果一个间隔完全在另一个间隔之前，那么查看下一个间隔，直到找到一个重叠或在其后的间隔。要么间隔A完全在间隔B之前，要么B完全在A之前，要么它们以某种方式重叠。一旦找到重叠，就可以停止查找。这可以轻松地返回最早的重叠对，但返回所有重叠对需要更多的工作。
伪代码:
Overlaps(actual[1..n], pending[1..m])
    i = 1
    j = 1
    while i <= n and j <= m do
        if actual[i].stop <= pending[j].start then
            i = i + 1
        else if actual[i].start >= pending[j].stop then
            j = j + 1
        else
            return true
    return false

注意 - 如果您想找到所有重叠的对，而不是在检测到第一个重叠后退出，您可以打印出i和j，并且如果actual[i].stop <= pending[j].stop，则增加i，或者如果actual[i].stop > pending[j].stop，则增加j。这将打印出每个重叠的对，并仍然保持线性时间。
问题在于当您发现重叠时该怎么办，因为需要检查所有可能的约会，而不是回到起点再次检查下一个可能的约会。 - user1480192
@user1480192，您想要一个能够返回所有重叠约会的方法吗？还是只需要一个方法来判断“您有重叠的约会”？我的方法正确回答了后者。或者您是在说这个方法不够高效吗？由于所有内容都已排序，可能可以使用某种二分查找之类的方法——我会好好考虑的。 - Patrick87
0
如果我们首先将这两个数组连接起来，连接所需的时间为O(n)，然后对整个数组进行排序，排序所需的时间为O(nlogn)，如果我们使用快速排序或归并排序，则计算总时间复杂度，如下所示：
F(n) = O(n) + O(nlogn)
因此最终的复杂度将是O(nlogn)，比O(n^2)更低。
0

您可以将现有和潜在的约会合并到一个数组中，并按开始时间对联合进行排序。为时间间隔添加标签，以确定是现有还是潜在的时间间隔。（您也可以将它们分别排序到不同的数组中，并递增两个索引，但使用一个列表的代码更简单）。

然后，您可以循环遍历组合数组，并在它们重叠时合并相邻的时间间隔。只合并现有的约会和现有的约会，同样地，只合并潜在的约会和潜在的约会。为此，您需要记住最近的现有和潜在的时间间隔。

通过这种方式，您不需要回到最开始的地方，只需要查看最近合并的时间间隔。

伪代码如下：

E: existing appointments
P: potential appointments

A: union of P and E, sorted by start time

lastE = []
lastP = []
for each appointment a in A:
    if a is existing:
        if a overlaps with lastE:
            lastE = lastE + [a]
        else
            lastE = [a]
        if a overlaps with lastP:
            print all appointments in lastP overlapping with a
    if a is potential:
        if a overlaps with lastE:
            print a
        if a overlaps with lastP:
            lastP = lastP + [a]
        else:
            lastP = [a]

请注意，您无需存储lastE的结构，可以将其定义为单个时间段并调整开始和结束时间。
但是，您需要了解lastP中的各个预约。通过在lastP中按结束时间维护降序，您可能甚至可以进一步优化它。然后，在打印出a和lastP之间的所有重叠时，您可以一旦看到lastP中潜在预约的结束时间小于a的开始时间，就可以停止查找。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接