如何在增加的距离落入另一个区间的区间中找到最小值

Question

假设我有一个区间[360420]，一个距离89和一组区间[480540]，[600660]，[100201080]和[1201260[第一区间上的第一个值加上落入391(391+89=480(中设置的区间之一的89

python中最有效的算法或实现是什么？

我知道有可能以1的增量循环通过第一个区间并得到结果，然而，我想知道是否有其他暴力的特定算法。。。

Answer 1

做一个集合交集并取最小值：

>>> interval = range(360, 420)
>>> distance = 89
>>> other_intervals = [range(480, 540), range(600, 660), range(1020, 1080), range(1200, 1260)]
>>> from functools import reduce
>>> min(
...     set(range(interval.start + distance, interval.stop + distance)) 
...     & reduce(set.union, map(set, other_intervals), set())
) - distance
391

Answer 2

这里有一个算法，它比迭代该范围内的每个整数快得多。相反，它在列表中的每个间隔上迭代，并使用比较和减法来找到所需的值。它是关于间隔列表的长度的O(n)复杂度，以及关于间隔的大小的O(1)复杂度。

class interval:
"An interval of the form [a, b["
def __init__(self, a, b):
self.a = a
self.b = b
def is_inside(self, other):
return any(other.a <= x < other.b for x in [self.a, self.b - 1])
def intersects(self, other):
return self.is_inside(other) or other.is_inside(self)
def find_intersection(self, others):
for i, other in enumerate(others):
if self.intersects(other):
# if other.a >= self.a, offset is the difference
# between other.a and self.a, otherwise self.a > other.a,
# so the lower bound of self is inside the other interval,
# so the offset is 0 away from the lower bound
offset = other.a - self.a if other.a >= self.a else 0
return i, offset
def __add__(self, offset):
return interval(self.a + offset, self.b + offset)

other_intervals = [interval(480, 540), interval(600, 660), interval(1020, 1080), interval(1200, 1260)]
# The interval [360, 420[ + 89 falls within the
# first interval in the list (index 0), and is 31 into
# the interval, (i.e. 360+31+89=480) hence the
# result (0, 31)
print((interval(360, 420) + 89).find_intersection(other_intervals))
# Neither a distance of 1 nor 100000 puts the
# first interval inside any of the others, so
# it returns None
print((interval(360, 420) + 1).find_intersection(other_intervals))
print((interval(360, 420) + 100000).find_intersection(other_intervals))
# 360 + 183 + 57 = 600, which is the lower bound of the
# second interval (index 1), hence the result (1, 57)
print((interval(360, 420) + 183).find_intersection(other_intervals))
# if the lower bound of the first interval is inside the
# other interval, the offset is 0: 360 + 121 = 481, whic
# is already inside [480, 540[, so nothing else needs to be added
print((interval(360, 420) + 121).find_intersection(other_intervals))

此函数返回间隔内的偏移量，例如问题中的示例为31。如果你想获得391，只需完成360+31即可。