Java 中用于查找时间重叠事件的数据结构

问题描述 投票:0回答:1

最好的解释方法是举例: 数据:[1,5]、[2,7]、[9,12]

输入:4 输出:[[1,5],[2,7]]

输入:8 输出:[]

输入:11 输出:[[9,12]]

是否有高效的 Java/Kotlin 来实现这一点? (也不会使 GC 超载)

java kotlin data-structures
1个回答
-1
投票

如果你想要快并且有足够的内存,你可以做下一步。

对于每个范围保留 3 个列表:

  1. 完全覆盖它的范围。
  2. 仅覆盖其左侧的范围
  3. 仅覆盖其右侧的范围。

对范围进行排序,以便您可以找到覆盖目标点的最短范围。

返回组 1 中的所有范围。过滤组 2 和组 3 以查找覆盖范围(您可以对它们列表进行排序以加快搜索速度)。

性能取决于结果中的范围数量。

© www.soinside.com 2019 - 2024. All rights reserved.