3

假设我有 N 个 [start,end] 形式的区间。我需要找出这些区间是否覆盖了整个范围。

例如：如果我的间隔是 [4.5,5.765] 和 [5.8,10] 并且间隔是 [5,10] 它应该报告错误，而对于相同的数据如果间隔是 [6,9.99] 它应该报告 true。

我需要 1e-9 的精度。间隔和范围将在 [-1000,1000] 内。

这个问题可以在 O(NlgN) 时间内解决吗？其中 N = 间隔数。

4

3 回答 3

2

O(N * log N)如果您对所有区间 ( )的起点和终点进行排序，那么O(N)您可以在一次传递中跟踪：

  • -1000和之间的数轴上的当前位置1000，它依次采用任何间隔的每个起点/终点。
  • “当前”打开了多少个区间，即在数轴上的这一点有多少个区间相交。

如果在此过程中的任何一点，当前值在目标范围内并且当前间隔数为 0，则目标范围不被间隔覆盖。如果在您到达目标范围的末端之前从未发生过这种情况，那么目标就被覆盖了。

由于区间是封闭的，请记住在具有 value的“起点”r 之前r对具有 value 的“结束点”进行排序，以确保在区间为[0,1]和[1,2]且目标为 的情况下返回“true” [0,2]。

IEEE 双精度足以满足1e-9+/-1000 范围内的粒度，但请注意5.8无法以二进制浮点数精确表示的问题。因此，根据计算间隔的方式，计算或表示错误可能会引入微小的“间隙”。出于这个原因，您可能希望在开始之前进行某种舍入到最接近的十亿分之一，和/或使用以 10 为底的而不是以 2 为底的表示所涉及的值。

于 2012-09-09T22:45:17.960 回答
1

虽然你已经得到了一些好的答案，但我想我会贡献一些简单明了的东西。

你还没有告诉我们间隔是否可以重叠，所以我假设它们可以。（否则，一个简单的 O(N) 搜索过程将告诉您您的范围是否在某个区间内。）

如果间隔集在多个范围内保持不变，最好的办法是根据它们的起点预先对间隔进行排序。（这通常是一个 O(N logN) 操作，但您只需执行一次）。然后，你可以这样做：

checkRange(range, intervals[])
    for each ( intv in intervals )
        if intv.start > range.start
            return false
        if intv.end >= range.end
            return true
        if intv.end > range.start
            range.start = interval.end

    return false

这只是一个 O(N) 通行证。

如果每个范围的间隔集可以更改，那么以下递归算法可能会或可能不会比每次对间隔进行排序更好：

delta = 1e-9

checkRange(range, intervals[])
    for each ( intv in intervals )
        if intv.start <= range.start and intv.end >= range.end
            return true
        if intv.end < range.start or intv.start > range.end
            continue
        if intv.start < range.start and intv.end > range.start
            range.start = interval.end
            continue
        if intv.start < range.end and intv.end > range.end
            range.start = interval.end
            continue
        range1 = new range(start = range.start, end = intv.start - delta)
        range2 = new range(start = intv.end + delta, end = range.end)
        intervals = intervals after intv
        return checkRange(range1, intervals) and checkRange(range2, intervals)

因为，对于数组或链表，您可以保留intervals after intv与原始相同的内存空间intervals[]，这仅使用一些堆栈空间进行递归迭代，仅此而已。至于计算复杂性，比我更好的人将不得不研究证明它的东西，但我觉得它可能相当不错。

于 2012-09-10T00:03:02.773 回答
0

您可以进行模糊排序。 最好的情况是O(n)和一般的情况O(n log n)。这类似于快速排序。最好的情况发生在所有区间中至少存在一个点，即它们都重叠。一般来说，重叠越多，算法比任何其他排序算法都更好。

下面是对该算法的详细分析。http://web.media.mit.edu/~dlanman/courses/cs157/HW3.pdf

于 2012-09-10T12:28:21.240 回答