algorithm - 适用于事件日历应用程序的最佳数据结构

Question

我有一个代表事件的类。 所以我们可以通过创建这个类的对象来创建一个事件。构造函数获取描述、开始时间、结束时间、邀请列表、位置 并返回一个用于唯一标识此对象的id。

Create events : (description, start time, end time, list of invites, location) -> id

现在这个类有另一个方法接受一个id并返回一个相应的事件对象

通过 id 获取事件:id -> 事件对象

类似地我们可以更新一个事件

更新事件->描述，开始时间，结束时间

现在我们要做的第四个操作是我们要过滤掉一个时间范围内的所有事件

获取事件:开始时间、结束时间

现在我必须使用/设计一个可以有效执行这 4 个操作的数据结构。 (我的意思是我们现在可以使用文件存储或缓存技术)

对于前三个操作，我认为我可以使用 Has map/table，它将 id 作为键，将对象作为值。 但在这种情况下，我将无法有效地执行第 4 个操作。

为此我再次使用 trie 数据结构。

Root Node->
      Month nodes (12 nodes)
      each month node will be having 30(or 31/28) children nodes. 
      and then those children nodes will be having time stamp nodes.

但在这种情况下，前三个操作变得有点低效。

我如何结合这两种数据结构来解决这个问题并高效地执行所有 4 个操作。或者是否有更好的数据结构可以完成这项任务。或者我们必须创建自己的自定义数据结构？

Answer 1

正如您所说，您可以使用 hashmap 进行第一个树操作。对于第 4 个操作，您可以维护 (start_time_of_event,id) 的排序列表。现在，要查找 (start,end) 之间的所有事件，您可以对该排序数组使用两次二分搜索，并查找 (start,end) 之间的所有事件。此方法的空间开销很小，因为您只需要存储事件的 id 和 start_date 的副本。