包含给定查询点的区间数

Question

我知道存在类似的问题here。我的问题也一样，我有 N 个间隔（有些可能重叠，有些甚至相同）。然后给出Q点查询，我需要告诉有多少个区间包含这个点。

我尝试通过对端点数组进行排序然后按照答案中提到的 +1、-1 技巧计算重叠间隔的数量来开发我的算法。但是在执行二进制搜索之后我应该做什么？因为并不总是这样，前缀和数组的对应索引就是答案。

e.g. 
Intervals are : [1,4] [5,7] [6,10] [7,13]
sorted end point array : [1,4,5,6,7,7,10,13]
+1/-1 array : [1,-1,1,1,1,-1,-1,-1]
prefix sum array : [1,0,1,2,3,2,1,0]

Query : 10
my algorithm gives 1 (corresponding prefix array)
but actual ans should be 2.

我该如何修正我的算法？

Answer 1

您链接的问题没有好的答案，所以：

第一个：

将每个区间的进出位置放入单独的数组中。（如果您使用闭区间，则退出位置为结束位置 + 1，即在 [4,6] 中，进入为 4，退出为 7.
对数组进行排序。

然后，对于每个点 p:

在入口数组中进行二分查找找到入口位置数<= p.
在退出数组中进行二分查找以找到退出位置数 <= p.
包含该点的区间数为entry_count - exit_count

注意位置数 <= p 是第一个元素的索引 > p。请参阅：Where is the mistake in my code to perform Binary Search? 以帮助您正确搜索。

以你的例子为例：

Intervals: [1,4], [5,7], [6,10], [7,13]
Entry positions: [1,5,6,7]
Exit positions: [5,8,11,14]
Entry positions <= 6:  3
Exit positions <= 6: 1
Intervals that contains 6:  3-1 = 2

Answer 2

问题是你的间隔是 [] 而不是 []，答案可能是针对后者。首先将您的结束索引转换为值 -1。

在此之后 + "compressing" 重复坐标你应该有：

 points = [1,5,6,7,8,11,14]
 sums = [1,0,1,1,-1,-1,-1]
 accumulated = [1,1,2,3,2,1,0]

然后查询，如果query < points[0] or query > points[max] return 0。如果不是，二分查找points得到index，答案在accumulated[index] .

包含给定查询点的区间数

Number of intervals that contains a given query point

arrays

sorting

algorithm

intervals