algorithm - 覆盖从 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])