两组间隔的差异

Question

我正在尝试编写一些代码来计算两组间隔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

Answer 1

使操作高效的唯一方法是保持间隔列表有序和不重叠(可以在其中完成O(n log n)).

如果两个列表都已排序且不重叠,则可以使用简单合并执行任何设置操作(并集,交集,差异,对称差异).

合并操作很简单:按顺序同时循环遍历两个参数的端点.(请注意,每个间隔列表的端点都是排序的,因为我们要求间隔不重叠.)对于发现的每个端点,确定它是否在结果中.如果结果当前具有奇数个端点且新端点不在结果中,请将其添加到结果中; 类似地,如果结果当前具有偶数个端点并且新端点在结果中,则将其添加到结果中.在此操作结束时,结果是端点列表,在间隔开始和间隔结束之间交替.

这是在python中:

# If using python 3, uncomment the following:
# from functools import reduce

# 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)