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

Question

我在编程竞赛中遇到了这个问题，但没能解决。

给定0到n的范围和以下列格式给出的一些数字对：

a1 b1
a2 b2
a3 b3
. .
. .
am bm

地点：0<=ai,bi<=n, 1<= n,m < 1,000,000

如果是ai<=bi，那么这对(ai,bi)涵盖了ai到bi之间的所有数字，包括它们本身，

否则，ai>bi就会对(ai,bi)覆盖ai到n和0到bi之间的所有数字，包括它们自己。

目标是找到最小的对数，以便覆盖0到n之间的整个范围。

编辑:如果不可能用所有的对覆盖整个范围，那么结果是-1。

Answer 1

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

首先，将这些对(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])

Answer 2

这就是我应该怎么做的，我相信它在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，当特定迭代的任何集合都不会从交集中生成更多元素时。

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