合并重叠间隔并尊重类型优先级

Question

假设我们有以下枚举：

// lower value takes precedence
enum Type{ 
  X(1), 
  Y(2), 
  Z(3); 
  ...
}

并记录：

record Interval(Type type, Instant startTime, Instant endTime){}

---

考虑到

Type

优先级，请考虑以下重叠间隔的示例：

     _____________
   1|   ZZZZZZZ
   2|YYYYYY
   3|    XXXXXXXXX

---

让我们将其分解为逐步迭代。

1. 按 ASC 顺序按

   startTime

   对间隔列表进行排序：

     _____________
   1|YYYYYY
   2|   ZZZZZZZ
   3|    XXXXXXXXX

2. 第一次迭代，只需将当前间隔添加到列表中即可：

     ______
   1|YYYYYY
--->|YYYYYY  (content of new merged intervals list)

3. 将新间隔添加到列表中，但缩小它，因为最后一个 Y 间隔具有优先权：

     __________
   1|YYYYYY
   2|   ZZZZZZZ
--->|YYYYYYZZZZ  (content of new merged intervals list)

4. X 间隔出现在第三次迭代中，优先于最后两次迭代。删除最后一个间隔并缩小最后一个之前的间隔：

     _____________
   1|YYYYYY
   2|   ZZZZZZZ
   3|    XXXXXXXXX
--->|YYYYXXXXXXXXX  (content of new merged intervals list)

正如你所看到的，我正在尝试合并这些间隔，但是那些

type

使一切变得更加困难，因为在某些情况下（例如第三次迭代）我必须搜索回我的列表。问题不仅在于前一个元素，还在于更进一步。这只是一个例子，事情可能要复杂得多。恐怕我必须返回并替换/缩小/删除堆栈中的几个间隔元素的情况是可能的。有人可以给我一个提示，如何优雅地处理这个问题吗？恐怕我解决这个问题的想法很糟糕......

Answer 1

对于每次事件创建一个包含

(time; type; boolean field for interval start/interval end)

的元组，创建这些元组的数组/列表

L

，并按时间字段对它们进行排序。

创建辅助列表

A

，用于按排序（按类型）顺序存储活动间隔。

浏览列表

L

。

当遇到间隔开始时，检查类型是否低于

A[0]

。如果是，则开始间隔输出，在

A

前面插入类型。如果没有，则使用二分查找在

A

中找到类型的位置，并将类型插入到相应的位置。

当遇到区间结束时，检查当前类型是否为A[0]。如果是，则终止输出间隔，使用

A[1]

（如果存在）开始新的输出间隔。从

A

列表中查找并删除类型。