用于在给定时间找到所有人还活着的快速算法？

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)坐标：死亡> =出生。

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

这些点都位于上三角形中，并且+是居住在日期D的人们的矩形区域。该矩形在左上方和左上方都是开放的。

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

我希望看到一个实现，尽管我不敢相信它具有速度优势。也许数量庞大。