我有一组具有整数值端点的时间间隔，例如 (1,2)、(2, 6) (5,6)，以及每个时间间隔内的事件数，我想确定它们是否我可以提取一组涵盖同一时期的互斥间隔，在本例中为 (1,2), (2, 5), (5,6)，其中 (2,5) 中的事件数由下式计算取 (2,6) 和 (5,6) 中数字的差。可能的重叠数量没有限制，例如它们都可以是 (n, 24) 的形式。我想知道这是否是标准解决方案的标准问题。
从更大的间隔集中提取详尽的互斥间隔
计算科学
算法
排序
2021-12-04 02:34:41
1个回答
我不知道您描述的问题的标准名称，但您可以使用标准数据结构来解决问题：区间树
您可以按顺序将每个区间插入树中，但只插入与树中已插入的任何区间不相交的区间部分。这样，当您构建树时，您可以保证树中只有互斥间隔。区间树旨在快速搜索重叠区间，因此所有这些搜索都不成问题。
这是一个算法：
- 令T为区间树（最初为空）
- 令L为区间列表
- 从L中弹出一个区间I
- 查询T以获取区间O重叠I的列表
- 将I与O中的每个区间相交。对于每个非空交叉点，从I中删除该交叉点（这将使I非常不相交），并使用来自I的事件计数更新O中间隔的事件计数。
- 添加从I到T的任何剩余非重叠间隔
- 如果L不为空，则转到第 3 步，否则转到第 8 步
- 查询所有区间的T。
最后一步为您提供具有适当事件计数的互斥间隔列表。
请注意，更新事件计数的方式需要进行一些试验。例如，您可能只想用I中重叠的事件计数的一部分而不是原始计数来更新O的重叠间隔中的事件计数。
其它你可能感兴趣的问题