java - 从事件对象打印所有时间间隔的好方法

Question

我正在使用一个包含开始和结束时间的事件对象。我想打印一些事件对象的数组列表的所有间隔，但是只能想到一种简单的蛮力解决方案。
假设我们的数组列表具有以下事件:

事件1:开始= 130，结束= 145

事件2:开始= 135，结束= 155

事件3:开始= 145，结束= 155

事件4:开始= 215，结束= 230

事件5:开始= 215，结束= 230

然后，我们将要打印如下内容:

130-135

135-145

145-155

215-230

到目前为止，我所能想到的就是根据开始时间对arraylist进行排序。对于每个开始时间，遍历整个列表，并选择最小的开始时间和结束时间中的最小值，该最小值大于该开始时间。当添加更多事件时，此解决方案似乎蛮力且效率低下。请注意，如果需要的话，我总是可以选择其他数据结构-我在间隔树上读了一点，但是不确定在这种情况下是否有用。

我正在寻找有关存储事件的最佳数据结构和打印所有有效间隔的好算法的建议(希望比我想到的要好)。任何建议，将不胜感激!

谢谢。

Answer 1

我建议使用一组链接列表。链表中的每个节点仅包括该节点内的间隔开始和结束时间，并且附加集合具有原始事件对象及其所有数据。

核心概念是，任何添加的事件都将其间隔按顺序排列在链接列表中，并且如果它与现有间隔以任何方式相交，则会对其进行拆分。如果您还希望支持删除事件，则删除的任何事件都会删除一个间隔或导致其中一些收敛。

间隔的打印输出内置于解决方案中:链接列表是按发生顺序排列的间隔(如您所描述的，没有重叠)，每个间隔中都固定有事件。无论关联事件的数量如何，您都可以迭代间隔并打印出节点。

一点符号:

se-事件

的开始时间

ee-事件

的结束时间

si-列表

中间隔节点的开始时间

ei-列表

中间隔节点的结束时间

为了描述构建此数据结构，首先描述如何向其中添加新事件。该算法针对不同的交集有很多情况，这使得它读起来有点长-但很容易编写代码:

结束案例:如果列表为空，请以事件开始和结束时间作为根创建一个新的列表节点，并创建其集合，并将新事件添加为集合中的第一个成员。

结束案例:如果您位于列表的末尾，请为新事件创建一个新的间隔列表节点，并将其连接到上一个节点。

如果当前列表节点完全大于事件时间(间隔发生在事件结束时间之后)-为新事件创建一个新的间隔列表节点，并将其放置在当前节点之前，并与先前的间隔节点正确链接。

如果当前列表节点完全小于事件时间(该间隔发生在事件开始时间之前)-向前移动一个节点。

如果当前列表节点完全包含在新事件中(间隔节点开始时间si在事件开始时间ei之后，并且间隔节点结束时间se在事件结束时间ee之前)-创建两个新的间隔节点，一个在当前时间间隔之前和之后，并将它们正确地链接起来-{se-si}{si-ei}{ei-ee}-将事件添加到所有三个关联的集合中。这两个新节点将仅在其集合中具有新事件，原始节点将具有其所有事件，并将新事件添加到集合中。

如果当前列表节点完全包含该事件(si在se之前，ee在ei之前)-为之前和之后创建两个新节点，正确链接它们，将时间间隔的事件集添加到新节点，更改中间节点的值是{se-ee}，因此您有一个链:{si-se}{se-ee}{ee-ei}。仅将新事件添加到中间节点持有的集合中。

如果当前列表间隔节点以事件开始，但在事件之前结束(se=si，但ei<ee)，则创建一个仅包含新事件的新节点{ei-ee}，并将其添加到当前节点之后(正确链接)，并将事件添加到当前列表节点。

(如果当前列表间隔节点以事件结尾，但在事件开始之后开始)(se>si，但ei=ee)，则在其集合中创建一个仅包含新事件的新节点{se-si}，并将其添加到当前节点之前(正确链接) )，并将事件添加到当前列表节点。

(如果当前列表间隔节点以事件开始但在间隔之前结束)(se=si，但ei>ee)，则创建一个新节点{ee-ei}，将所有现有列表节点事件复制到其集合中并添加新事件，并将其链接到当前节点。还将当前节点从{si-ei}更改为{si-ee}。

(如果当前列表节点在事件之前开始，但它们一起结束)(se<si，但ei=ee)，则创建一个新节点{se-si}，将所有现有列表节点事件复制到其集合中并添加新事件，并将其链接在当前节点之前。还将当前节点从{si-ei}更改为{se-ei}。

如果当前列表间隔节点在事件开始后开始，并且在事件结束后也结束(se<si和ee<ei)，则在当前节点周围创建两个新节点，并像以前一样将当前间隔更改为-{se-si}{si-ee}{ee-ei}。此三重奏中的第一个间隔将仅在其集合中具有新事件，中间的间隔将具有所有原始节点的集合以及新事件，而最后一个将仅具有原始节点的集合。

如果当前列表间隔节点在事件开始之前开始，并且在事件结束之前也结束(se>si和ee>ei)，请在当前节点周围创建两个新节点，并像以前一样将当前间隔更改为-{si-se}{se-ei}{ei-ee}。此三重奏中的最后一个间隔将仅在其集合中具有新事件，中间的间隔将具有所有原始节点的集合以及新事件，而第一个间隔将仅具有原始节点的集合。

，最后，如果事件与间隔完全匹配，则将其添加到集合中。

结果是您有了一个不重叠且按时间顺序排列的间隔列表，您可以遍历它们以进行打印而不会出现问题，并且可以针对每个间隔说出在该间隔发生的事件。您可以轻松地修改算法的实现以包括删除事件，或者如果您需要搜索它，则可以将其从链接列表更改为数组列表以使用二进制搜索。