问覆盖从0到n的所有整数的最小对

EN

我相信以下贪婪的算法应该有效。

首先，将这些对(x, y)按x排序(您可以将x > y对拆分为[0, y]，[x, n])。现在，选择第一个，并将指针current设置为第一个间隔。

然后，将current指针移动到具有x <= current.y和最大y (最大y大于当前的y)的对上。

最后，检查[first_pick.x, last_pick.y]是否涵盖了您的范围，如果没有，则检查输出-1。

示例：

1 3
3 7
3 4
4 9
4 10
4 8
5 9

选1 3。我们继续从这个位置对数组进行扫描，并将电流设置为3 7，因为这仍然是与第一个间隔相交的，并且具有最大的y。到目前为止，我们选择了：

1 3
3 7

从这里继续扫描，选择4 10，我们就完成了：

1 3
3 7
4 10
=> [1 10] covered

这在O(n^2)中很容易实现，在排序之后也可以在O(n)中实现，方法是跟踪上一个被选中的元素和第二个被选中的元素。然后，对于被考虑的对，您可以决定是使该对成为新的最后一个被选中的元素，还是去掉当前的最后一个被选中的元素，并将其替换为当前考虑的对。

# after the sort
pick first
for i = 1 to len(given pairs):
  if pairs[i].x <= picked[-1].y and pairs[i].y > picked[-1].y:
    if len(picked) > 1 and pairs[i].x <= picked[-2].y:
      picked[-1] = pairs[i]
    else:
      picked.append(pairs[i])

这就是我应该怎么做的，我相信它在O(n^2)时间内运行。

让我们使用集合抽象。将每一对映射到它所涵盖的一组整数。这就抽象出了a和b之间的比较，所以对于n = 6，(1, 5) = {1, 2, 3, 4, 5}，(3, 1) = {0, 1, 3, 4, 5, 6}。

然后我们要覆盖一组0到n的整数，调用这个G(对于目标)。

使用贪婪的方法，我们迭代从对生成的所有集合，并找到与G相交元素最多的集合。从G中删除这些元素，并将1添加到计数器中。

使用for循环进行迭代，并在没有剩下的元素时完成。或者返回-1，当特定迭代的任何集合都不会从交集中生成更多元素时。

每次迭代时，我们都会缩小目标集的大小，并选择包含剩余元素的大多数元素的对。因此，当我们完成时，我们得到了最低限度的保证。