给定一个间隔，在间隔列表中查找所有间隔
假设我有一个这样的范围列表
[[1,3]，[2,5]，[4,6]，[8,10]，[12,15]，[13,17]
现在我想找到一个范围，比如[3,11]。我的算法应该给我这个范围的所有范围。例如，这个的输出应该是
<代码>输出-[1,3]、[2,5]、[4,6]、[8,10]
我该如何着手解决这个问题？
PS：我知道段树可能会有所帮助。我可以在其中构建树来存储间隔并查询位于间隔内的Point，但如何在给定间隔的情况下获取所有间隔。
共有1个答案
区间树绝对是您需要的数据结构。我也面临同样的问题，为了提高性能，我使用了增广区间树，其中每个节点除了范围的边界外，还包括与节点子树的最大值相关的信息。
您可以在这里找到一个深入的解释和Java实现：数据结构：用于搜索重叠间隔的增强间隔树
-
与其查询具有开始和结束日期的间隔列表，不如从列表中检索仅与搜索开始和结束日期重叠的所有间隔，最好的方法是： 使用整数示例，以整数间隔列表为例。在此列表中，以下是所有唯一的间隔集，其中每组中的每个间隔都相互重叠： 以下是DateInterval的类： 我将收到按开始时间排序的间隔列表，如下所示： （在这个示例列表中，开始日期和结束日期总是均匀地落在一小时上。但是，它们可以落在任何一秒上（或者毫秒）。
-
这与寻找重叠的间隔有关。给定一个间隔列表（间隔树），我知道如何做到这一点。我有一个间隔列表。例如， 结果应该是 [2,3], [7,8] 我需要做的是找到所有列表中常见的间隔列表。 我认为这个问题类似于合并列表。问题是我无法应用列表的成对合并。应用此方法可能会导致丢失重叠间隔。因此，我需要将所有列表合并在一起，一次考虑所有列表（而不是成对）。 我可以使用间隔树。将每个列表中的第一个间隔插入间隔树并
-
我试图解决以下问题：给定N个时间间隔，每个时间间隔指定为（开始，结束），不重叠，根据开始排序——找到一个包含给定日期的时间间隔。例如： 3人进入第一节，15人进入第四节，以此类推。 到目前为止，我有以下基本想法： 我们可以使用二进制搜索来找到相应的间隔（logn） 由于可能只有少数时间间隔较大，其余时间间隔较小，因此根据时间长短对itervals进行排序可能是值得的。然后，在统计上，大多数情况下，
-
间隔有开始和结束时间。间隔可能重叠。可能有几个包含时间t的间隔。只返回其中一个就可以了。 这是一个面试问题。我能够解决这个问题，方法是根据结束对间隔进行排序，根据开始对另一个时间进行排序，并取具有匹配开始和结束的间隔的交点。显然有更多优化的解决方案。 这里有一个例子：[1,5][2,10][3,6][2,9]，目标是8。在这种情况下，[2,10]和[2,9]中的任何一个都是正确答案。 我想问题的关
-
您将获得两个间隔列表，
-
问题内容： 我有下表，其中包含每15分钟从几个不同的设备读取的值： 我想在表中找到每个月在给定月份中没有条目的所有设备的所有差距。对于上表，结果应该是这样的： 该表大约有35000台设备和1亿个条目。 这是我尝试过的；它很慢，但是返回我需要的。但是，除了速度之外，还有另一个问题：它只能找到在给定月份设备的最后一个条目之前丢失的时间间隔；之后的所有内容都将被忽略，因此有可能会错过额外的缺失值间隔。