1 
R1=[0,20]
R2=[15,20]
R3=[30,50]
Target=[0,50]

我需要检查目标范围是否被所有 R(s) 覆盖。

在上面的例子中 0..20 和 30..50 被覆盖，但不包括 20..30

有没有简单的方法来检查它？

遍历所有数字会降低性能，因为实际上我需要处理 10000 个范围。

我可以在服务器端使用 Python-django 或在客户端使用 jquery。

4

6 回答 6

3

Using sympy:

from sympy import Interval

coverage = Interval(0,20) + Interval(15,20) + Interval(30,50)
target = Interval(0, 50)

return coverage.subset(target)

Or if you need actual result:

>>> target - coverage
(20, 30)
于 2013-05-17T14:11:50.560 回答
1

除非您的范围按顺序存储，否则您将不得不访问每个范围，因为一个范围可能包含最小/最大值。因此，对于 N 个范围，您可能拥有的最差运行时间将是 O(N)。所以是这样的：

Ranges = [[0,20],[15,20],[30,50]]
def inRange(targetMin,targetMax,Ranges):
    minV,maxV = Ranges[0][0], Ranges[0][1]
    for r in Ranges:
        if r[0] < minV:
                minV = r[0]
        if r[1] > maxV:
                maxV = r[1]
        if targetMin >= minV and targetMax <= maxV: #if we're in range, no need to check the others
                return True
    else:
        return False

print(inRange(0,50,Ranges))

或非累积（其中 min/max 是每个范围的本地，而不是所有范围）

def inRangeNonCum(targetMin,targetMax,Ranges):
    for r in Ranges:
        if targetMin >= r[0] and targetMax <= r[1]:
                return True
    else:
        return False

print(inRangeNonCum(0,20,Ranges))
print(inRangeNonCum(30,50,Ranges))
print(inRangeNonCum(20,30,Ranges))

生产

>>> 
True
True
False

您的预期结果。在任何一种情况下，最坏的时间都是 O(N)。如果您的范围以某种方式排序，那么您可以查看末端，如果末端的最小值大于 targetMax，然后说从末端向后看 1/4 的范围等...

于 2013-05-17T11:50:34.003 回答
0

使用这个算法

#Added a few ranges for demonstration puposes
ranges = [[25, 35], [0, 20], [5, 10], [15, 20], [30, 50]]

new_ranges = []

for range in sorted(ranges):
    for large_range in new_ranges:
        if range[0] >= large_range[0] and range[0] <= large_range[1]:
            if range[1] > large_range[1]:
                large_range[1] = range[1]
            break
    else:
        new_ranges.append(range)

print new_ranges

[[0, 20], [25, 50]]

new_ranges包含合并范围。通常，如果您的范围被覆盖，它将仅包含在合并范围之一中。对它们进行排序后，搜索它们的速度非常快。

于 2013-05-17T12:11:02.267 回答
0

对于 Python集来说，这似乎是一个自然问题——直到经验证明你需要更快的东西。

ranges = [ [0,20], [15,20], [30,50] ]
target = [0,50]
result = set(range(target[0], target[1]))

for a,b in ranges:
    result.difference_update(range(a, b))

print result  # set([20, 21, 22, 23, 24, 25, 26, 27, 28, 29])
于 2013-05-17T12:23:10.400 回答
0 
ranges = [[0,20],[15,20],[30,50]]
target=[x for x in range(0,50+1)]
for x, y in ranges:
    range_object = range(x, y+1)
    target = list(filter(lambda x: x not in range_object, target))
    if not target:
        break

print("Not covered:" + str(target))

这应该有效，并为您提供未涵盖的内容。它必须遍历所有数字，但通过使用过滤器功能应该相当有效。

编辑：与@njzk2 提出的范围合并结合使用时效果最佳

于 2013-05-17T12:07:16.033 回答
0

您可以使用区间库：

import interval
r1 = interval.Interval(*R1)
r2 = interval.Interval(*R2)
r3 = interval.Interval(*R3)
t = interval.Interval(*Target)

In [11]: r = interval.IntervalSet([r1, r2, r3])

In [12]: r
Out[12]: IntervalSet([Interval(0, 20, lower_closed=True, upper_closed=True),
                      Interval(30, 50, lower_closed=True, upper_closed=True)])

In [13]: t_minus_r = interval.IntervalSet([t]) - r

In [14]: t_minus_r
Out[14]: IntervalSet([Interval(20, 30, lower_closed=False, upper_closed=False)])

您可以简单地测试一个值是否在给定的 Interval/IntervalSet 中：

In [15]: 1 in r
Out[15]: True

In [16]: 1 in t_minus_r
Out[16]: False

In [17]: 20.00001 in t_minus_r
Out[17]: True
于 2013-05-17T12:08:00.953 回答