覆盖从 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之间的所有数字，包括他们自己，

else ai>bi then pair (ai,bi) 涵盖了 ai 到 n 和 0 到 bi 之间的所有数字，包括它们自己。

objective就是求最小对数，使得0到n之间的整个范围都被覆盖。

编辑：如果不可能用所有对覆盖整个范围，则结果为 -1。

Answer 1

这就是我会做的，我相信它在 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 循环迭代，当我们没有更多元素时结束。或者 return -1，当特定迭代的集合中的 none 从交集生成更多元素时。

每次我们迭代时，我们都会减少目标集的大小，并选择覆盖剩余元素最多的一对。因此，我们保证完成后的最低限度。

Answer 2

我相信下面的贪心算法应该可行。

首先，将 (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，因为它仍然与第一个间隔相交并且具有最大的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])

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

Minimum pairs to cover all integers from 0 to n

language-agnostic

algorithm