查找重叠区间中的所有区间（重叠和非重叠）

Question

我的问题与这里提出的问题非常相似： 在重叠间隔中查找基本间隔

我喜欢那里给出的最佳解决方案，但由于我需要保留一条额外的关键信息，我需要对算法进行一些调整/进一步解释。作为背景，这些数字是数据库中参与者的年龄范围。我需要计算重叠，以便我可以在重叠的研究实验室之间平均分配参与者，如果没有重叠，我可以将所有参与者分配给那个实验室。

这就是我得到的：

Interval    Lab
{75, 105}    A
{100, 120}   B
{100, 130}   C

这是我想从输入中得到的（所以我知道要查询什么）：

Interval    Lab(s)
{75, 100}    A
{100, 105}   A, B, C
{105, 120}   B, C
{120, 130}   C

使用上一个问题中给出的顶级算法，我可以轻松得到嵌套：{75, 100, 105, 120, 130} 这导致间隔：{75, 100} {100, 105} {105, 120} { 120、130}。这很好，但现在我不知道哪些间隔对应哪些实验室（无需再次遍历列表，逐个检查每个实验室，这可能效率低下）。

谁能向我解释如何轻松做到这一点？感谢您的帮助！

Answer 1

使用关联的实验室创建第二个阵列

{A, [B,C], A, B, C}
{75, 100, 105, 120, 130}

在创建间隔时，请保持一组正在运行的实验室。当您点击索引 i 时，如果它不存在，则添加第 i 个实验室，如果存在，则将其删除。将每个新间隔 i 到 i+1 与集合中的项目相关联。

例如，

i = 0; set = {A}; interval = 75-100; 
i = 1; set = {A,B,C}; interval = 100-105; 
i = 2; set = {B,C}; interval = 105-120; 
i = 3; set = {C}; interval = 120-130;