我正在尝试编写一些代码来计算两组间隔 A - B 的差异，间隔端点是整数，但我正在努力提供有效的解决方案，任何建议将不胜感激 示例：[(1, 4), (7, 9)] - [(3,5)] = [(1, 3), (7, 9)]
好吧，这是我迄今为止尝试过的最好的（两个列表已经排序）
class tp():
def __repr__(self):
return '(%.2f,%.2f)' % (self.start, self.end)
def __init__(self,start,end):
self.start=start
self.end=end
z=[tp(3,5)] #intervals to be subtracted
s=[tp(1, 4)),tp(7, 9), tp(3,4),tp(4,6)]
for x in s[:]:
if z.end < x.start:
break
elif z.start < x.start and z.end > x.start and z.end < x.end:
x.start=z.end
elif z.start < x.start and z.end > x.end:
s.remove(x)
elif z.start > x.start and z.end < x.end:
s.append(tp(x.start,z.start))
s.append(tp(z.end,x.end))
s.remove(x)
elif z.start > x.start and z.start < x.end and z.end > x.end:
x.end=z.start
elif z.start > x.end:
continue
使操作高效的唯一方法是保持区间列表排序且不重叠（这可以在
O(n log n)两个列表都排序且不重叠，任何集合操作（联合、交集、差异、对称差异）都可以通过简单的合并来执行。
合并操作很简单：同时按顺序循环遍历两个参数的端点。 （请注意，每个区间列表的端点都是排序的，因为我们要求区间不重叠。）对于发现的每个端点，决定它是否在结果中。如果结果当前有奇数个端点并且新的端点不在结果中，则将其添加到结果中；类似地，如果结果当前有偶数个端点并且新端点在结果中，则将其添加到结果中。在此操作结束时，结果是端点列表，在间隔开始和间隔结束之间交替。
这是在 python 中：
# In all of the following, the list of intervals must be sorted and
# non-overlapping. We also assume that the intervals are half-open, so
# that x is in tp(start, end) iff start <= x and x < end.
def flatten(list_of_tps):
"""Convert a list of intervals to a list of endpoints"""
return reduce(lambda ls, ival: ls + [ival.start, ival.end],
list_of_tps, [])
def unflatten(list_of_endpoints):
"""Convert a list of endpoints, with an optional terminating sentinel,
into a list of intervals"""
return [tp(list_of_endpoints[i], list_of_endpoints[i + 1])
for i in range(0, len(list_of_endpoints) - 1, 2)]
def merge(a_tps, b_tps, op):
"""Merge two lists of intervals according to the boolean function op"""
a_endpoints = flatten(a_tps)
b_endpoints = flatten(b_tps)
sentinel = max(a_endpoints[-1], b_endpoints[-1]) + 1
a_endpoints += [sentinel]
b_endpoints += [sentinel]
a_index = 0
b_index = 0
res = []
scan = min(a_endpoints[0], b_endpoints[0])
while scan < sentinel:
in_a = not ((scan < a_endpoints[a_index]) ^ (a_index % 2))
in_b = not ((scan < b_endpoints[b_index]) ^ (b_index % 2))
in_res = op(in_a, in_b)
if in_res ^ (len(res) % 2): res += [scan]
if scan == a_endpoints[a_index]: a_index += 1
if scan == b_endpoints[b_index]: b_index += 1
scan = min(a_endpoints[a_index], b_endpoints[b_index])
return unflatten(res)
def interval_diff(a, b):
return merge(a, b, lambda in_a, in_b: in_a and not in_b)
def interval_union(a, b):
return merge(a, b, lambda in_a, in_b: in_a or in_b)
def interval_intersect(a, b):
return merge(a, b, lambda in_a, in_b: in_a and in_b)
区间
[a, b)[b, c)b[a,c)这是一个函数的示例实现，它将任意间隔列表归一化为排序的、非重叠的间隔。
def interval_normalise(a):
rv = sorted(a, key = lambda x: x.start)
out = 0
for scan in range(1, len(rv)):
if rv[scan].start > rv[out].end:
if rv[out].end > rv[out].start: out += 1
rv[out] = rv[scan]
elif rv[scan].end > rv[out].end:
rv[out] = tp(rv[out].start, rv[scan].end)
if rv and rv[out].end > rv[out].start: out += 1
return rv[:out]
这可以用扫描线算法来解决。这个想法是将两个集合的所有区间起点保留在一个排序数组中，并将终点保留在另一个排序数组中，用它们属于哪个集合的信息标记它们。例如
A B
[(1, 4), (7, 9)] - [(3,5)]
A: start:[1,7] end:[4,9], B: start:[3]end:[5]
start:[(1,a),(3,b),(7,a)]
end: [(4,a),(5,b),(9,a)]
现在有两个指向每个数组开头的指针。在循环中增加一个指向最低值的添加间隔，从 a 开始直到它们以 b 或 a 结束。例如对于上面我们将按此顺序迭代点
(1,a) (3,b) (4,a) (5,b) (7,a) (9,a)
# and adding intervals where we have seen an start a and an end a or b
(1,3) (7,9)
这导致在间隔数方面的线性解决方案。
另一个使用 numpy 的实现。我假设，正如我认为使用 integer endpoints 更自然，间隔是封闭的。 对于我在下面建议的方法，我们绝对需要处理（半封闭）区间，包括 -infinity 和 +infinity。
def merge_intervals(intervals):
# Normalize to sorted non-overlaping intervals. Aimilar idea as in
# https://www.geeksforgeeks.org/merging-intervals/
if len(intervals)==0: return intervals
assert np.all(intervals[:,0]<=intervals[:,1]), f"merge_intervals: intervals not well defined. intervals={intervals}"
if len(intervals)==1: return intervals
intervals = np.sort(intervals.copy(),axis=0)
stack = []
# insert first interval into stack
stack.append(intervals[0])
for i in intervals[1:]:
# Check for overlapping interval,
# if interval overlap
if i[0] > stack[-1][1]+1:
stack.append(i)
else:
stack[-1][1] = max(stack[-1][1], i[1])
return np.array(stack)
def union_intervals(a,b):
return merge_intervals(np.r_[a,b])
# The folowing is the key function. Needs to work
# well with infinities and empty sets.
def complement_intervals(a):
if len(a)==0: return np.array([[-np.inf,np.inf]])
a_normalized = merge_intervals(a)
result0 = np.r_[-np.inf,a_normalized[:,1]+1]
result1 = np.r_[a_normalized[:,0]-1,np.inf]
non_empty = np.logical_and(result0 < np.inf, result1 > -np.inf)
result = np.c_[result0[non_empty],result1[non_empty]]
if np.array_equal(result,np.array([[np.inf,-np.inf]])):
result = np.array([])
return merge_intervals(result)
def intersection_intervals(a,b):
union_of_complements = union_intervals(complement_intervals(a),complement_intervals(b))
return complement_intervals(union_of_complements)
def difference_intervals(a,b):
return intersection_intervals(a,complement_intervals(b))