我正在使用一个包含开始和结束时间的事件对象。我想打印一些事件对象的数组列表的所有间隔，但是只能想到一种简单的蛮力解决方案。
假设我们的数组列表具有以下事件:
事件1:开始= 130，结束= 145
事件2:开始= 135，结束= 155
事件3:开始= 145，结束= 155
事件4:开始= 215，结束= 230
事件5:开始= 215，结束= 230
然后，我们将要打印如下内容:
130-135
135-145
145-155
215-230
到目前为止，我所能想到的就是根据开始时间对arraylist进行排序。对于每个开始时间，遍历整个列表，并选择最小的开始时间和结束时间中的最小值，该最小值大于该开始时间。当添加更多事件时，此解决方案似乎蛮力且效率低下。请注意，如果需要的话，我总是可以选择其他数据结构-我在间隔树上读了一点，但是不确定在这种情况下是否有用。
我正在寻找有关存储事件的最佳数据结构和打印所有有效间隔的好算法的建议(希望比我想到的要好)。任何建议，将不胜感激!
谢谢。
最佳答案
我建议使用一组链接列表。链表中的每个节点仅包括该节点内的间隔开始和结束时间，并且附加集合具有原始事件对象及其所有数据。
核心概念是，任何添加的事件都将其间隔按顺序排列在链接列表中，并且如果它与现有间隔以任何方式相交，则会对其进行拆分。如果您还希望支持删除事件，则删除的任何事件都会删除一个间隔或导致其中一些收敛。
间隔的打印输出内置于解决方案中:链接列表是按发生顺序排列的间隔(如您所描述的，没有重叠)，每个间隔中都固定有事件。无论关联事件的数量如何，您都可以迭代间隔并打印出节点。
一点符号:
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}。此三重奏中的最后一个间隔将仅在其集合中具有新事件，中间的间隔将具有所有原始节点的集合以及新事件，而第一个间隔将仅具有原始节点的集合。 结果是您有了一个不重叠且按时间顺序排列的间隔列表，您可以遍历它们以进行打印而不会出现问题，并且可以针对每个间隔说出在该间隔发生的事件。您可以轻松地修改算法的实现以包括删除事件，或者如果您需要搜索它，则可以将其从链接列表更改为数组列表以使用二进制搜索。
关于java - 从事件对象打印所有时间间隔的好方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46652809/