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!

No, this is volunteer work for the database I help manage

LeoPardus
– LeoPardus

2012-06-12 02:18:15 +00:00
Commented Jun 12, 2012 at 2:18 — LeoPardus
– LeoPardus, Commented Jun 12, 2012 at 2:18

dfb · Accepted Answer · 2012-06-12 05:18:10Z

5

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;

edited Jun 12, 2012 at 5:18

answered Jun 12, 2012 at 3:13

dfb

13.3k2 gold badges33 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

LeoPardus Over a year ago

Thank you for the response. I kind of see the idea, but could could you explain it more clearly? Can you give an example of an interval i to i+1 and what the corresponding items in the set would be (and how you would get it from the diagram you used above)?

Stanly Over a year ago

Hi @leo, did you find the optimized solution for this problem. I am also having a similar problem?

Collectives™ on Stack Overflow

Finding all intervals (overlapping and nonoverlapping) in overlapping intervals

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related