时间戳

首页 > 解决方案 > 包含给定查询点的区间数

arrays - 包含给定查询点的区间数

问题描述

我知道这里存在类似的问题。我的问题也相同，我有 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.

我应该如何修复我的算法？

标签： arraysalgorithmsortingintervals

解决方案

您链接的问题没有很好的答案，因此：

第一的：

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

然后，对于每个点 p：

  1. 在条目数组中进行二进制搜索以找到条目位置的数量 <= p。
  2. 在出口数组中进行二分搜索以找到出口位置的数量 <= p。
  3. 包含该点的区间数为 entry_count - exit_count

请注意，位置数 <= p 是第一个元素 > p 的索引。请参阅：执行二进制搜索的代码中的错误在哪里？帮助您正确进行搜索。

对于您的示例：

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

推荐阅读