给定一些整数范围，找到一个最小的集合，至少包含每个范围中的一个整数。

Question

如何找到一组最小数量的整数，使得对于给定的整数范围，对于每个范围，该集合至少包含一个整数。例如，如果我有以下这些范围：

[0, 4], [1, 2], [5, 7], [6, 7], [6, 9], [8, 10]

然后一些解集是：{ 1, 6, 8 }, { 2, 7, 9 }, { 1, 7, 8 }等。

- scarecrow

Answer 1

想象一下，你把所有范围按结束值排序，就像在日程表中安排会议一样。

你可以用一种贪心的方式来选择数字，即首先选择最先结束的片段（在你的例子中，这将是2）。

然后你删除包含该数字的所有部分，并重新开始。

这个算法将产生解决方案{ 2, 7, 10 }

0  1  2  3  4  5  6  7  8  9 10
   ----
-------------
      ^        -------
      |           ----
                  ----------
                     ^  -------
                     |        ^
                              |

- alestanis

Answer 2

算法： 对起点和终点进行排序。依次遍历它们，直到遇到一个端点。将其添加到答案中并删除所有已经通过起点的区间（即包含当前端点的区间）。重复此过程直到没有点为止。

示例：

[0, 4], [1, 2], [5, 7], [6, 7], [6, 9], [8, 10]

排序后将变为：

[0, [1, 2], 4], [5, [6, [6, 7], 7], [8, 9], 10], ans = []

第一个端点是2]，我们将其添加到ans并删除在其之前开放的范围，即[0和[1:

[5, [6, [6, 7], 7], [8, 9], 10], ans = [2]

现在第一个端点是7]，我们要移除范围[5, 7]，[6, 7]，[6, 9]：

[8, 9], ans = [2, 7]

最后加上9并删除最后一个范围。结果将为[2, 7, 9]。

复杂度：

排序需要O(nlogn)的时间，之后您将两次传递每个元素：一次是查找下一个端点时，一次是删除所有当前打开的间隔，这是线性的，总复杂度将是O(nlogn)，来自排序。

- Grigor Gevorgyan

---

与其将起始点和终点一起排序，我们也可以这样做： 根据结束点对（起始点，结束点）对进行排序。然后从开头开始扫描。首先，我们存储第一对的终点，并将其添加到解集中。然后，只要配对的起始点低于存储的终点，我们就向前扫描。每当我们找到一个其起始点大于存储点的对时，我们将该对的终点添加到解集中，并将该终点存储在上一个存储点的位置上。我们继续进行此处理直到最后一对。 - scarecrow

Answer 3

我们按结束数字对区间进行排序。对于任何一个区间，如果它的开始不大于前一个结束（由于区间已经排序，因此结束不会小于前一个结束），则在前一个结束处存在重叠，可以跳过此区间。如果当前区间的开始大于前一个结束，则没有重叠，将当前结束添加到结果集中。

考虑区间 (0, 3), (2, 6), (3, 4), (6, 10)。排序后，我们得到 (0, 3), (3, 4), (2, 6), (6, 10)。我们从 result = [3] 和 previous = 3 开始。由于 3 <= previous，因此我们跳过区间 (3, 4)；previous 保持不变。由于 2 <= previous，因此我们跳过区间 (2, 6)；previous 保持不变。最后，由于 6 > previous，我们将 10 添加到结果中，并更新 previous = 10。算法终止；答案是 [3, 10]。

时间复杂度： n log(n)，其中 n 是区间的数量。

- Abhijit Sarkar