计算不被任何一组区间覆盖的最小正整数

Question

几周前有人在这里发布了这个问题，但它看起来非常像没有事先研究的家庭作业，OP在获得一些反对票后立即删除了它。

不过，这个问题本身很有趣，我已经想了一个星期，没有找到令人满意的解决方案。希望有人能帮忙？

问题如下：给定一个N个整数间隔的列表，其边界可以取从0到N³的任何值，找到最小的整数i使得i不属于任何输入间隔。

例如，如果给定列表（N=4），则算法应返回9。

我能想到的最简单的解决方案运行在O（n log（n））中，它包括三个步骤：

• 通过增加下限对间隔进行排序
• • 如果最小下界是

  这个简单的解决方案运行在O（n log（n））中，但最初的海报写道，算法应该运行在O（n）中。如果已经对间隔进行了排序，那么这很简单，但OP给出的示例包括未排序的间隔。我想这一定与N³有关，但我不确定是什么。。。散列？线性时间排序？欢迎提出想法。

  以下是上述算法的粗略python实现：

  def merge(first, second):
      (a, b), (c, d) = first, second
      if c <= b + 1:
          return (a, max(b, d))
      else:
          return False
  
  def smallest_available_integer(intervals):
      # Sort in reverse order so that push/pop operations are fast
      intervals.sort(reverse = True)
  
      if (intervals == [] or intervals[-1][0] > 0):
          return 0
  
      while len(intervals) > 1:
          first = intervals.pop()
          second = intervals.pop()
  
          merged = merge(first, second)
          if merged:
              print("Merged", first, "with", second, " -> ", merged)
              intervals.append(merged)
          else:
              print(first, "cannot be merged with", second)
              return first[1] + 1
  
  print(smallest_available_integer([(3,5), (2,8), (0,3), (10,13)]))
  

  输出：

  Merged (0, 3) with (2, 8)  ->  (0, 8)
  Merged (0, 8) with (3, 5)  ->  (0, 8)
  (0, 8) cannot be merged with (10, 13)
  9
  

Answer 1

另一个想法是以某种方式使用这些间隔的补码。假设C（）为您提供了一个区间的补码，例如C（[3,5]）将是小于3和大于5的整数。如果最大值为N^3，那么使用模N^3 1，甚至可以将其表示为另一个间隔[6，（N^3 1）2]。

如果您想要一个不属于任何原始区间的数字，那么这些区间的所有补码中都应该存在相同的数字。然后，它归结为编写一个函数，可以计算任何两个这样的“补码区间”的交点。

我还没有实现这个想法，因为我的纸笔图纸表明，在计算这样的交集时需要考虑的情况比我最初想象的要多。但我认为这背后的想法是有效的，它会导致O（n）算法。

编辑

经过进一步思考，有一个最坏的情况，使事情比我原先想象的更复杂。

Answer 2

详细说明@mrip的评论：您可以在O（n）时间内使用您描述的精确算法，但更改排序算法的工作方式。

通常，基数排序使用基数2：根据元素的位是0还是1将元素分成两个不同的桶。每轮基数排序需要时间O（n），并且每位有一轮最大的数字。调用最大的nunber U，这意味着时间复杂度为O（n log U）。

但是，您可以将基数排序的基数更改为其他基数。使用基b，每一轮都需要时间O（nb），因为初始化和迭代bucket需要时间O（b），将元素分配到bucket需要时间O（n）。然后是对数b轮。这给出了O的运行时间（（n b）log_bU）。

这里的诀窍是，由于最大数字U=n^{3，您可以设置b=n并使用基数n排序。现在轮数为log_{nU=lognn3，每轮需要O（n）个时间，因此对数字进行排序的总工作量为O（n）。更一般地说，对于任意k，可以在时间O（kn）内对[0，nk]范围内的数字进行排序。如果k是固定常数，则这是O（n）时间。}}

结合原始算法，这在时间O（n）内解决了问题。

希望这有帮助！