找到所有的間隔重疊的間隔

Question

我的問題是非常相似的一個問這裏（重疊和不重疊）： Finding elementary intervals in overlapping intervals

我想給那裏的頂級解決方案，但我需要的算法的一些調整/進一步的解釋由於我需要保留一個額外的關鍵信息。正如背景一樣，這些數字是數據庫中參與者的年齡範圍。我需要計算重疊，以便我可以在重疊的研究實驗室之間平均分配參與者，如果沒有重疊，我可以將所有參與者分配給該實驗室。

這就是我得到：

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

與相關實驗室（S）

{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;