我在一次编程竞赛中遇到了这个问题，但是无法解决。
给定一个 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。
最佳答案
我相信下面的贪心算法应该可行。
首先，对 (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])
关于algorithm - 覆盖从 0 到 n 的所有整数的最小对数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30403804/