6

我正在尝试解决以下问题：给定 N 个时间间隔，每个时间间隔指定为（开始，结束），不重叠，基于开始排序 - 找到一个包含给定日期的时间间隔。例如给出：

[1,4] [5,8] [9,10][11,20]

3 属于第一个区间，15 属于第四个区间，以此类推。

到目前为止，我有以下基本想法：

  1. 我们可以使用二分查找找到对应的区间（Log N）
  2. 由于可能只有少数间隔较大，其余间隔较小，因此可能值得根据其持续时间对迭代进行排序。然后，从统计上讲，大多数时候我们会“达到”最长的间隔 (O(1))，只是有时这会导致 N 的最坏情况复杂度。

我在想是否有结合这两种方法的空间。另一种想法是根据持续时间进行排序并将所有间隔插入树中，并按开始日期进行比较，在最坏的情况下，当最长持续时间按时间顺序排列时，这种方法的性能等于 2。

我想象的理想解决方案是有一棵树（或一些类似的数据结构），它在顶部包含最长的间隔，然后两个分支将具有接下来的两个最长间隔等。但是，我看不出有什么方法可以分支那棵树，即由于我们明确假设我们根据长度插入，我们不能真正丢弃树的左侧或右侧。

任何意见将不胜感激。

4

6 回答 6

4

O(1)在大多数情况下和最坏的情况下，这两种方法的天真组合提供了 a O(logN)，但大 O 表示法中的隐藏常数将是双倍的：

  1. 让原始数组为intervals
  2. 创建第二个数组，按照建议按间隔长度降序排序。随它去lengths
  3. 对于每个查询，intervals使用二分搜索和lengths线性搜索进行搜索。搜索将并行1完成，第一个完成 - 将导致另一个也停止。

因为在第 3 步中，我们可能会在 中进行最多c*log(n)步骤的二分查找intervals，所以我们将整体进行最多2*c*log(n)步骤。如果我们在 中更快地找到元素lengths，它将导致二分查找在中间结束，我们将减少操作次数，（但使用双常量，然后是原始方法）。

(1) 不需要并行计算机，可以通过逐步搜索，模拟单线程并行计算，直到找到答案。（一般信息，理解答案不需要：S.Even、A.Itai 和 A.Shamir 在他们的文章On the Complexity of TimeTable and Multi Commodity Flow Problems中介绍了“并行搜索”的概念）

于 2012-12-24T10:08:53.667 回答
3

您可以优先考虑二叉搜索树中的某些节点并使其保持平衡：

从您的组合方法开始（将较长的间隔放置在靠近顶部的位置）并使用一系列旋转来使二叉搜索树平衡（在破坏一些优先级的同时，如果它们不破坏，它应该保留靠近根的高优先级节点余额）。

要平衡树，请尝试以下策略（未经测试）：

  • 平衡左半部分（根的子树）
  • 平衡右半边
  • 如果右半边比左半边高 1 以上（AVL 平衡条件
    • 虽然这是真的
      • 如果右-左四分之一（右半的左半部分）高于右-右四分之一，则将右子树向右旋转（启动 AVL 双旋转）
      • 将树向左旋转（完成一次 AVL 旋转）
      • 平衡左半部分（左半部分已经平衡 - 从 #3 开始）
  • 否则，如果左半边比右半边高 1 以上
    • 做另一种情况的相反

这应该会产生一个尽可能尊重原始优先级的 AVL 平衡树。

于 2012-12-24T10:06:23.067 回答
0

有可能将两者结合在一起。这是我的想法，

根据范围的长度构建二叉树，假设我们有以下范围，

a: [0, 1), b: [1, 2), c: [3, 10), d: [11, 12), e: [13, 14)

我们从底部构建树，我们根据范围大小组合叶子，所以第一轮我们可以得到内部叶子，

(a, b), c, (d, e)

然后，

(a, b, c), (d, e)

根将是，

(a, b, c, d, e)

在每一轮中，我们结合具有最小范围长度的节点，保持在树的深度。

每个节点指向左、右子节点，并保持子节点的最小值、最大值。

如有不妥请指出..

于 2012-12-24T09:51:22.700 回答
0

我会这样做：

使用第一个和最后一个间隔的数据（平均持续时间和时间），从统计上估计您希望时间处于哪个间隔。如果该间隔不包含目标，请使用估计的间隔重新执行估计数组结束（另一端将是最近的实际结束）。

于 2012-12-24T10:06:02.393 回答
0

我使用JodaTime和 TimeSlots（几乎等同于 Joda Period）实现了类似的东西。Period 是我的自定义类，具有 DateTime 类型的开始和结束。我持有一个按结束日期排序的期间树集。

时隙类：

public class TimeSlot<T> {
    private DateTime start;
    private DateTime end;

    // accessors
    ...
}

实用方法：

public TimeSlot<T> getTimeSlot(DateTime pointInTime) {
    for (TimeSlot<T> ts : getCounterTimeSlotSet()) {
        if (ts.getPeriod().isDateInRange(pointInTime)) {
            return ts;
        }
    }
    return null;
}


public boolean isDateInRange(DateTime date) {
    if (date == null) {
        return false;
    }

    return date.isAfter(this.start.minusMillis(1)) 
        && date.isBefore(this.end.plusMillis(1));
}

最近我找到了实现艾伦区间代数的库，你可能会觉得它很有用。

于 2012-12-24T10:13:03.377 回答
0

你可能是对的，二进制搜索不会是最优的，奇数分布。虽然，N = 10 亿的 log_2(N) 仅为 30 左右。

如果要搜索的列表中的每个元素的可能性相同，则元素的二进制搜索是最佳的。

因此，多级二分搜索在这里可能是理想的，其中每个级别的间隔大小大致相同。使用给出的示例：

First Level: [1-10] [11-20] # Size = 10
Second Level: [1-10] = [1,4] [5,8] [9,10] # Size = 4

如果在 11 到 20 之间，则完成，否则展开 [1-10] 并检查区间 [1,4] [5,8] [9,10]。

设置搜索结构需要考虑 O(N log(N)) 向上的一些额外成本，并且对于小间隔来说成本更高，但如果最大和之间有足够大的差距，它应该有一个相当好的平均搜索时间最小的区间大小。

在最坏的情况下，您将拥有 log(N) 级别。

于 2012-12-24T11:05:16.950 回答