贪心算法，用于寻找与所有其他区间重叠的最小区间集
我正在学习贪婪算法，遇到了一个我不知道如何解决的问题。给定一组开始时间为a，结束时间为b的区间（a，b），给出一个贪婪算法，该算法返回该集合中每隔一个区间重叠的最小区间数。例如，如果我有：
(1,4) (2,3) (5,8) (6,9) (7,10)
我将返回（2,3）和（7,8），因为这两个区间覆盖了集合中的每个区间。我现在得到的是：
- 通过增加结束时间对间隔进行排序
- 将结束时间最小的间隔推到堆栈上
- 如果一个区间（a，b）与堆栈顶部的区间（c，d）重叠（所以a小于d）
我的问题是：这个算法是如何贪婪的？我在与这些概念作斗争。所以也许我有这个权利，也许我没有，但是如果我有，我就不知道贪婪的规则是/应该是什么。
编辑：下面提出了一个有效的观点，关于这一点我应该更清楚。（7,8）代替（1,10）（涵盖所有内容），因为（7,8）中的每一次都在（5,8）（6,9）和（7,10）中。与（2,3）相同，每次都有in（1,4）和（2,3）。我们的目标是获得一组时间间隔，这样，如果您查看该组时间间隔中所有可能的时间，则每次都至少在一个原始时间间隔中。
共有1个答案
贪婪算法是一种反复选择最佳增量改进的算法，即使从长远来看它可能是次优的。
我觉得你的算法并不贪婪。这个问题的贪婪算法是：
- 从输入集中找出包含在最大间隔数中的间隔。
对于本例，它将首先生成（7,8），因为它包含在3个输入间隔中，然后将输入集减少到（1,4）（2,3），然后生成（2,3）
请注意，此算法不会为输入集（0,4）（1,2）（1,4）（3,6）（3,7）（5,6）生成最佳输出
它首先产生（3,4），因为它被4个输入区间覆盖，但最好的答案是（1,2）（5,6），每个区间覆盖3个区间
-
考虑一个问题来寻找区间图的最小支配集。在区间调度的上下文中，它被转换为以下问题： 存在多个可能相互重叠的间隔。找到区间的最小子集，以便对于未包含在子集中的每个区间，它将在与它重叠的子集中找到至少1个区间。 有一个公认的贪婪解决方案可从互联网上的各种来源，例如康奈尔大学的一个解决方案：http://www.cs.cornell.edu/Courses/cs4820/2011sp/handouts/s
-
给定一个数字向量，我想找到大小为2的组合中最小的绝对差异。然而，摩擦点伴随着使用来创建保持成对的矩阵。当矩阵/向量太大时，如何处理问题？ 当使用得到的对数（列数）太大时，我得到以下错误： 矩阵中的错误（r，nrow=len.r，ncol=count）：无效的“ncol”值（太大或NA） 这篇文章指出，矩阵的大小限制大约是10亿行和两列。 这是我使用的代码。抱歉在我的函数输出中使用了——我正在解决H
-
问题内容： 我正在使用Java实现RSA加密程序。现在我正在使用 素数。这是产生的随机数。我需要测试各种加密速度。 我的问题是： 使用什么算法？ 上面的算法与其他算法（例如Rabin-Miller，Fermats，Lucas-Lehmer）有什么区别？ 谢谢。 问题答案： 的可能素数方法同时使用Miller-Rabin和Lucas-Lehmer算法来测试素数。 请参阅内部方法。
-
我有一组可能重叠的输入日期范围。我想创建具有调整日期的新日期范围，而不是组合这些重叠的日期范围，例如： 最终应为： 有没有有效的方法用Java解决这个问题？ 提前感谢！ 更新：在我的第一个问题中，我没有提到我自己的方法，所以它是这样的：我简单地获取间隔的开始和结束日期，并将其添加到一个排序的集合中。之后，我会遍历集合并根据重新排序的日期创建新的间隔。
-
本文向大家介绍查找C ++中所有区间的交集，包括了查找C ++中所有区间的交集的使用技巧和注意事项，需要的朋友参考一下 假设我们有N个间隔，形式为{L，R}，L是开始时间，R是结束时间。我们必须找到所有间隔的交集。相交是位于所有给定间隔内的间隔。如果找不到，则返回-1。例如，如果间隔类似于[{1，6}，{2，8}，{3，10}，{5，8}，则输出间隔为{5，6} 为了解决这个问题，我们将按照以下步
-
我需要找到一种算法来解决以下问题： 给出了一个区间列表（leftBound、RightBound），这是在此行为中对区间进行分组的最有效算法： 间隔：（1,4）、（6,9）、（1,3）、（4,8）、（6,9）、（2,7）、（10,15） 需要的解决方案： 组（2,3）包含（1,3), (1,4), (2,7) 组（6,8）包含（4,8), (6,9) 组（10,15）包含（10,15） 当然，有不