多时间区间最小取值合并及高效更新方案问询

我有一组包含start_ts、end_ts和value的时间区间数据：

[
  {
    "start_ts": "2022-10-24T01:00:00",
    "end_ts": "2022-10-27T04:00:00",
    "value": 20
  },
  {
    "start_ts": "2022-10-25T03:00:00",
    "end_ts": "2022-10-26T04:00:00",
    "value": 14
  },
  {
    "start_ts": "2022-10-22T01:00:00",
    "end_ts": "2022-10-25T11:00:00",
    "value": 25
  },
  {
    "start_ts": "2022-10-24T01:00:00",
    "end_ts": "2022-10-27T04:00:00",
    "value": 22
  },
  ...
]

需要生成无重叠的时间区间列表，每个区间对应时段内的最小value，示例输出如下：

[
  {
    "start_ts": "2022-10-22T01:00:00",
    "end_ts": "2022-10-24T01:00:00",
    "value": 25
  },
  {
    "start_ts": "2022-10-24T01:00:00",
    "end_ts": "2022-10-25T03:00:00",
    "value": 20
  },
  {
    "start_ts": "2022-10-25T03:00:00",
    "end_ts": "2022-10-26T04:00:00",
    "value": 14
  },
  {
    "start_ts": "2022-10-26T04:00:00",
    "end_ts": "2022-10-27T04:00:00",
    "value": 20
  }
]

当前算法存在大量边界情况难以维护，该问题是天际线问题的反向变体，且需要支持快速插入/更新新数据（原算法复杂度约O(n log(m))，插入复杂度约log(n)），希望得到更简洁高效的解决方案。

核心方法：扫描线+延迟删除最小堆 #

这个问题的核心是追踪时间轴上各时段的最小覆盖值，用扫描线思路可以避免复杂的区间合并边界处理，同时结合延迟删除堆实现高效插入。

步骤1：事件建模与存储 #

• 把每个原始区间拆成两个事件：
  • 「加入事件」：时间为start_ts，携带value，表示该值从此时开始生效。
  • 「移除事件」：时间为end_ts，携带value，表示该值从此时停止生效。
• 使用有序数据结构（如平衡BST、跳表）存储所有事件，按时间戳排序；若时间戳相同，优先处理「移除事件」——避免同一时间点因先加后删导致的无效最小值计算。

步骤2：扫描事件并生成结果 #

• 初始化：
  • 最小堆：实时维护当前生效的value集合的最小值。
  • 延迟删除哈希表：记录需要从堆中移除的value的计数（解决普通堆无法高效删除任意元素的问题）。
  • 结果列表：存储最终的无重叠区间。
  • prev_time：记录上一个事件的时间戳，初始为第一个事件的时间。
• 遍历排序后的事件：
  1. 生成区间：如果prev_time < 当前事件时间且堆不为空，说明两个事件之间的时段有生效值，将{start_ts: prev_time, end_ts: 当前事件时间, value: 堆顶值}加入结果列表。
  2. 处理事件：
     • 若是「加入事件」：将value推入堆。
     • 若是「移除事件」：在延迟删除哈希表中对应value的计数加1。
  3. 清理无效堆顶：检查堆顶元素，如果其在延迟删除表中的计数>0，弹出堆顶并减少对应计数，直到堆顶为有效元素或堆为空。
  4. 更新prev_time为当前事件时间。

步骤3：支持快速插入的优化 #

• 插入新区间时，只需向有序事件结构中添加两个事件，时间复杂度为O(log N)（N为总事件数）。
• 延迟删除机制让堆的插入/清理操作保持O(log K)复杂度（K为当前生效的value数量），无需遍历堆删除元素。

关键边界处理 #

• 空堆时段：如果扫描过程中堆为空，说明该时段没有任何区间覆盖，无需生成结果条目。
• 重复时间戳：同一时间点的多个事件合并处理，避免生成长度为0的无效区间。
• 重复value：延迟删除表用计数而非布尔值，处理同一value多次加入/移除的场景。

示例验证 #

针对输入数据，事件排序后依次处理：

1. 2022-10-22T01:00:00（加入25）：堆顶为25，prev_time更新为此时间。
2. 2022-10-24T01:00:00（加入20）：生成[2022-10-22, 2022-10-24, 25]区间，推入20后堆顶为20，更新prev_time。
3. 2022-10-24T01:00:00（加入22）：无区间生成，推入22后堆顶仍为20，更新prev_time。
4. 2022-10-25T03:00:00（加入14）：生成[2022-10-24, 2022-10-25T03:00, 20]区间，推入14后堆顶为14，更新prev_time。
5. 2022-10-25T11:00:00（移除25）：延迟删除表中25计数+1，堆顶仍为14，无区间生成，更新prev_time。
6. 2022-10-26T04:00:00（移除14）：生成[2022-10-25T03:00, 2022-10-26T04:00, 14]区间，延迟删除表中14计数+1，清理堆顶后堆顶为20，更新prev_time。
7. 2022-10-27T04:00:00（移除20）：生成[2022-10-26T04:00, 2022-10-27T04:00, 20]区间，延迟删除表中20计数+1，清理堆顶后堆顶为22，更新prev_time。
8. 2022-10-27T04:00:00（移除22）：延迟删除表中22计数+1，清理堆顶后堆为空，无后续区间。

最终生成的结果与示例完全一致。

复杂度分析 #

• 初始构建：O(N log N)（N为原始区间数，每个区间生成2个事件，排序事件的复杂度）。
• 单次插入：O(log N)（插入事件到有序结构） + O(log K)（堆操作），满足要求的高效插入。
• 生成结果：O(M log K)（M为事件总数，每个事件处理含堆清理操作）。

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