例如，考虑一组不重叠的范围。
Range 1 - [100,150]
Range 2 - [180.200]
Range 3 - [250,300]
有效输入可以是 [100,110] , [115,130] , [185,195] , [250,300] ;这些都包含在 3 个范围之一内。前两个输入范围属于范围 1，第三个属于范围 2，最后一个属于范围 3。
无效输入(未包含在 3 个范围之一内)包括 [80,90] , [310,320] , [160,170] , [80,190] , [80,110] , [180,320] , [260,310] 。
输入范围的问题实际上存在，在该范围内不是问题。我只想知道给定范围是否适合给定范围集中的任何特定范围。
除了线性和二分搜索来找出这个问题之外，我们有什么方法可以在恒定时间内完成(使用散列或任何技术)。如果时间不是恒定的，是否有更优化的解决方案？
最佳答案
这一切都与存储有关目标范围的信息的数据结构有关。为您的问题提供 O(1) 解决方案的数据结构是可能的，但不一定非常有吸引力。例如，我们可以构造一个数组，该数组对于整个空间中的每个(可表示的)值都有一个条目，该整个空间可以被任何感兴趣的范围覆盖，并在每个元素中存储覆盖该范围的范围(如果有)的索引。当然，这可能需要大量内存，并且将目标范围加载到这样的数据结构中的成本与其大小成正比。
如果您需要目标范围的紧凑表示，特别是如果您想要一个大小独立于范围大小的表示，那么我认为您没有比这样做更好的了按一个端点对范围进行排序，并使用二分搜索来定位目标范围。这相当于在(平衡)二叉搜索树中记录范围，并在树中搜索目标范围。考虑到已经构建了适当的数据结构，解决问题的成本在目标范围的数量上将是 O(log n)。
关于c - 如何在恒定时间内检查一组非重叠范围内的范围，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53506672/