java - 在给定时间找到所有人活着的快速算法？

Question

假设你有类似的东西

class Person {
  LocalDate bornOn;
  LocalDate diedOn;
}

假设您有一堆“Person”实例，您可以按照自己喜欢的方式存储它们。

编写一个可以列出给定时间所有活着的人的高效函数的最佳方法是什么？

数据结构也应该高效可变，特别是在添加新元素方面。

即概念上类似于

List<Person> alive(List<Person> people, LocalDate date) {
  return people.stream().filter(x -> x.bornOn.compareTo(date) <= 0 && x.diedOn.compareTo(date) > 0).collect(Collectors.toList())
}

只会更高效。

我的第一个直觉是有两个 NavigableMaps

NavigableMap<LocalDate, Person> peopleSortedByBornOn;
NavigableMap<LocalDate, Person> peopleSortedByDiedOn;

可以使用给定日期的 headMap()/tailMap() 查询每个查询，这些查询的交集将是结果。

有没有更快或更方便的解决方案？甚至可能是支持此类操作的某种广泛使用的 Java 集合/映射类型？

Answer 1

我想提一下几何数据结构，比如四叉树。出于理论目的。有 (born, died) 坐标:died >= born.

    d         b=d
    |    | - /
    | +  |  /
    |    | /
  D |____|/
    |   /:
    |- / :
    | /  :
    |/___:_____ b
         D

所有点都位于上三角，+ 是生活在日期 D 的人的矩形区域。矩形的左端和上端是开放的。

有几何数据结构就可以了。并且有可以处理此类几何查询的数据库。

我很想看到一个实现，尽管我不会打赌速度优势。也许数量巨大。