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

Question

我怎样才能找到一组最小数量的整数，以便对于某些给定的整数范围，对于每个范围，该集合至少包含一个整数。例如，如果给我这些范围：

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

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

Answer 1

想象一下，您绘制所有按最终值排序的范围，就像您在日程安排器中绘制会议一样。

您可以以贪婪的方式直观地选择您的数字，以便第一个是首先完成的段（在您的示例中，这将是2）。

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

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

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

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)来自排序。

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是区间数。