Finding all intervals (overlapping and nonoverlapping) in overlapping intervals

Question

My question is very similar to the one asked here: Finding elementary intervals in overlapping intervals

I like the top solution given there, but I need some tweaking/further explanation of the algorithm due to an extra key piece of information I need to retain. Just as background, these numbers are age ranges of participants in a database. I need to figure the overlaps so that I can split the participants evenly between the overlapping research labs, and if there are no overlaps, I can give all of the participants to that one lab.

This is what I get:

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

This is what I want to get from the input(so I know what to query):

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

Using the top algorithm given in the previous question, I can easily get the nesting: {75, 100, 105, 120, 130} This results in the intervals: {75, 100} {100, 105} {105, 120} {120, 130}. This is great, but now I don't know which intervals correspond to which labs (without making another pass through the list, checking each lab one by one, which can be inefficient).

Can anyone explain to me how to do this easily? Thank you for your help!

Answer 1

Create a second array with the associated lab(s)

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

As you create your intervals keep a running set of labs. As you hit index i, add the ith lab if it doesn't exist, if it does, remove it. Associate each new interval i to i+1 with the items in the set.

e.g.,

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;