python - 合并两个间隔列表，其中一个列表具有优先级

Question

我现在遇到了一个算法问题，我想优化它的复杂性。
我有两个区间列表S = [[s1, s2], [s3, s4], ..., [sn-1, sn]]和W = [[w1, w2], [w3, w4], ..., [wm-1, wm]]要按照顺序合并，s的区间优先于w的区间（s表示强，w表示弱）。
例如，这一优先权意味着：
S = [[5,8]]和W = [[1, 5], [7, 10]]将给出：res = [[1, 4, W], [5, 8, S], [9, 10, W]]。这里从w开始的间隔优先于s的间隔
S = [[5, 8]]和W = [[2, 10]]将给出：res = [[2, 4, W], [5, 8, S], [9, 10, W]]。这里W的间隔被分成两部分，因为S有优先权。
在合并这些列表时，我需要通过在每个间隔旁边写入第三个元素（我们可以称之为符号）来跟踪这些间隔的强弱性质这就是为什么结果是这样的：[[1，4，w]，[5，8，s]，[9，10，w]]。
最后，由于所有间隔的并集不覆盖某个范围内的所有整数，因此我们有第三个符号，例如b表示空白，填充缺少的间隔：[[1, 2, W], [5, 8, S], [9, 10, W], [16, 20, S]]将被填充为：[1, 2, W], [3, 4, B], [5, 8, S], [9, 10, W], [11, 15, B], [16, 20, S]]
我的第一次尝试是非常幼稚和懒惰（因为我首先想让它发挥作用）：
如果这两个区间列表中包含的最大整数是m，那么我创建了一个m大小的列表，其中填充了b个符号：res = [B]*M = [B, B, B ..., B]
然后，我首先从w开始一个接一个地取间隔，并在此间隔中重写索引res中的元素，将其符号更改为w。接下来，我对间隔s执行相同的操作，并且由于在最后一步中用符号s覆盖，因此优先权得到尊重。
它给出了如下信息：
[B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B]
[B, B, B, W, W, W, W, B, W, W, W, W, B, W, W, B, B]
[B, B, S, S, W, W, W, B, S, S, W, W, B, S, W, B, B]
最后，我最后一次遍历大列表，将间隔分解并用相应的符号重新创建间隔。前面的示例给出：
[[1, 2, B], [3, 4, S], [5, 7, W], [8, 8, B], [9, 10, S], [11, 12, W], [13, 13, B], [14, 14, S], [15, 15, W], [16, 17, B]]
不幸的是，可预见的是，这个算法在实际中是不可用的：在我的应用程序中，m大约是1000000，如果我没有弄错的话，这个算法是o（n2）。
所以，我想一些建议和方向来解决这个算法复杂性问题。我确信这个问题看起来像是一个著名的算法问题，但我不知道该怎么办。
我的一些改进的想法现在可以用来优化算法，但是实现起来相当复杂，所以我认为有更好的想法但它们在这里：
执行相同的覆盖过程以尊重优先级：在列表w中，在需要尊重优先级时插入带覆盖的s间隔。然后填写此列表，用B符号插入缺少的间隔。但是，由于案例太多，我们会大量使用if来比较间隔。
在逐步浏览S和W的同时构造一个新列表在这个想法中，我们将有一个逐列表光标从一个间隔转到另一个间隔，直到两个列表中的一个结束再次，我们使用了很多if和case，我们在新列表中插入了优先级的间隔。但在大量的案件中，这也提出了同样复杂的问题。
我希望我说得很清楚，如果不是的话，我可以用另一种方式来解释。
请教我经验和智慧：）
谢谢
编辑：这是我的“天真”算法代码：

def f(W, S, size):

  #We first write one symbol per sample
  int_result = ['B'] * size
  for interval in W:
      for i in range(interval[0], interval[1]+1):
          int_result[i] = 'W'
  for interval in S:
      for i in range(interval[0], interval[1]+1):
          int_result[i] = 'S'

  #we then factorize: we store one symbol for an interval of the same    symbol.    
  symbols_intervals = []
  sym = int_result[0]
  start = 0
  for j in range(len(int_result)):
      if int_result[j] != sym:
          symbols_intervals.append([start, j-1, sym])
          sym = all_symbols[j]
          start = j
      if j == len(int_result)-1:
          symbols_intervals.append([start, j-1, sym])

  return symbols_intervals

Answer 1

你幼稚的方法听起来很合理，我认为它的时间复杂度是O（nm），其中n是你试图解决的间隔数，m是你试图解决的区间。你可能遇到的困难是，你还有O（m）的空间复杂度，这可能会占用一段相当长的内存。
这里有一种合并的方法，而不需要构建一个“主列表”，这可能更快，因为它把间隔视为对象，复杂性不再与M联系在一起。
我将一个区间（或区间列表）表示为一组元组(a,b,p)，每个元组指示从a到b的时间点，包括整数优先级p（W可以是1，而S可以是2）在每个间隔中，必须是ab的情况。优先考虑更高的优先级。
我们需要一个谓词来定义两个区间之间的重叠：

def has_overlap(i1, i2):
    '''Returns True if the intervals overlap each other.'''
    (a1, b1, p1) = i1
    (a2, b2, p2) = i2
    A = (a1 - a2)
    B = (b2 - a1)
    C = (b2 - b1)
    D = (b1 - a2)
    return max(A * B, D * C, -A * D, B * -C) >= 0

当我们发现重叠时，我们需要解决它们。这种方法考虑到这一点，并尊重优先权：

def join_intervals(i1, i2):
    '''
    Joins two intervals, fusing them if they are of the same priority,
    and trimming the lower priority one if not.

    Invariant: the interval(s) returned by this function will not
    overlap each other.

    >>> join_intervals((1,5,2), (4,8,2))
    {(1, 8, 2)}
    >>> join_intervals((1,5,2), (4,8,1))
    {(1, 5, 2), (6, 8, 1)}
    >>> join_intervals((1,3,2), (4,8,2))
    {(1, 3, 2), (4, 8, 2)}
    '''
    if has_overlap(i1, i2):
        (a1, b1, p1) = i1
        (a2, b2, p2) = i2
        if p1 == p2:
            # UNION
            return set([(min(a1, a2), max(b1, b2), p1)])
        # DIFFERENCE
        if p2 < p1:
            (a1, b1, p1) = i2
            (a2, b2, p2) = i1
        retval = set([(a2, b2, p2)])
        if a1 < a2 - 1:
            retval.add((a1, a2 - 1, p1))
        if b1 > b2 + 1:
            retval.add((b2 + 1, b1, p1))
        return retval
    else:
        return set([i1, i2])

最后，merge_intervals取一定的间隔并将它们连接在一起，直到不再有重叠：

import itertools

def merge_intervals(intervals):
    '''Resolve overlaps in an iterable of interval tuples.'''
    # invariant: retval contains no mutually overlapping intervals
    retval = set()
    for i in intervals:
        # filter out the set of intervals in retval that overlap the
        # new interval to add O(N)
        overlaps = set([i2 for i2 in retval if has_overlap(i, i2)])
        retval -= overlaps
        overlaps.add(i)
        # members of overlaps can potentially all overlap each other;
        # loop until all overlaps are resolved O(N^3)
        while True:
            # find elements of overlaps which overlap each other O(N^2)
            found = False
            for i1, i2 in itertools.combinations(overlaps, 2):
                if has_overlap(i1, i2):
                    found = True
                    break
            if not found:
                break
            overlaps.remove(i1)
            overlaps.remove(i2)
            overlaps.update(join_intervals(i1, i2))
        retval.update(overlaps)
    return retval

我认为这是最坏的时间复杂度O（N = 4），虽然平均情况下应该很快。无论如何，您可能希望将此解决方案与更简单的方法进行比较，以查看哪些方法更适合您的问题。
据我所见，我的merge_intervals适用于您的示例：

# example 1
assert (merge_intervals({(5, 8, 2), (1, 5, 1), (7, 10, 1)}) ==
        {(1, 4, 1), (5, 8, 2), (9, 10, 1)})

# example 2
assert (merge_intervals({(5, 8, 2), (2, 10, 1)}) ==
        {(2, 4, 1), (5, 8, 2), (9, 10, 1)})

要用空白（b）间隔覆盖该情况，只需添加另一个间隔元组，该元组以优先级覆盖整个范围：

# example 3 (with B)
assert (merge_intervals([(1, 2, 1), (5, 8, 2), (9, 10, 1),
                         (16, 20, 2), (1, 20, 0)]) ==
        {(1, 2, 1), (3, 4, 0), (5, 8, 2),
         (9, 10, 1), (11, 15, 0), (16, 20, 2)})