带类型优先级的重叠区间合并问题求解

定义说明 #

优先级枚举（值越小优先级越高） #

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

区间记录类型 #

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

重叠区间示例 #

_____________
   1|   ZZZZZZZ
   2|YYYYYY
   3|    XXXXXXXXX

原合并步骤尝试 #

1. 按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)

现有问题 #

当前合并思路存在缺陷：由于类型优先级的存在，新加入高优先级区间时需要回溯已合并的区间列表，甚至可能要修改多个已合并元素，实现起来繁琐且容易出错，求优雅的解决思路。

优雅解决思路 #

方法一：事件点拆分法 #

• 提取关键时间点：收集所有区间的startTime和endTime，按时间排序并去重，得到时间节点序列t0, t1, t2, ..., tn。
• 筛选每个时间片段的最高优先级类型：遍历每个时间区间[ti, ti+1)，找出所有覆盖该片段的原区间，选取其中Type值最小（优先级最高）的类型。
• 合并连续同类型片段：将相邻的、类型相同的时间片段合并为一个完整的Interval。

这个方法无需回溯，逻辑直观：拆分后的小片段独立处理，直接取最高优先级，最后合并连续同类型即可得到结果。

方法二：按优先级从高到低处理 #

• 排序原区间：将所有区间按Type优先级升序（即Type值从小到大）排序，优先处理高优先级区间。
• 维护高优先级区间集合：每处理一类优先级的区间时，先对同优先级的区间做常规重叠合并，再将合并后的区间中未被已处理高优先级区间覆盖的部分加入结果集合。
• 填充低优先级空隙：后续低优先级区间仅能填充高优先级区间未覆盖的时间范围，不会修改已有的高优先级区间。

以示例为例，先处理X区间，再处理Y区间（仅保留Y中不与X重叠的前半段），最后处理Z区间（所有部分都被X、Y覆盖，无新增内容），最终结果与预期一致，全程无需回溯调整已合并区间。

内容的提问来源于stack exchange，提问作者DeadLine