Compare Multiple Ranges and Return Non-Overlapping Sets

Question

If I have ranges of numbers and I need to return the sets that do not overlap with one another For example, here is a set of numbers:

1,4
0,3
4,7
0,4

I need to return:

0,3
4,7

An example of a larger data set:

0,1
0,2
2,5
4,8
3,7
8,11
8,9
9,11

I would need to return:

0,2 
3,7 
8,11

It would need to account for situations where if a smaller set is in another and should be discarded. Using the previous set,

0,1
0,2
3,7

Since 0,1 is contained within 0,2 set 0,1 should be discarded.

Any help would be appreciated. Thanks much.

if one range is 0-2 [0,1,2] and the other range is 0-1 [0,1], 1 is between 0-2 and therefore 0,1 should be discarded. Does that help? — AnonPyDev
– AnonPyDev, Commented May 13, 2016 at 20:00

Adrian Rutkowski · Accepted Answer · 2016-05-13 19:54:00Z

1

If your goal is to find the largest set of non-overlapping sets you should check Interval scheduling problem, especially solution using greedy algorithm. If performance doesn't matter you can try playing with python set union or subset and compare sets with each other.

set(range(0, 4)).union(set(range(0, 1)))

edited May 13, 2016 at 19:54

answered May 13, 2016 at 19:48

Adrian Rutkowski

3392 silver badges7 bronze badges

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

3 Comments

AnonPyDev Over a year ago

The goal is to find the largest non-overlapping sets within a group that would sit next to each other. For example, 0,4 and 5,8 and 9,11 so that set 3,10 would be discarded.

Ecko Over a year ago

You might want to play with recursive functions to find ones that sit next to each other. Not sure quite how to do it though.

AnonPyDev Over a year ago

Thanks for referring me to interval scheduling. It is what I was looking for, I was able to modify the following code to get the result needed: github.com/farazdagi/algorithms/blob/master/…

Collectives™ on Stack Overflow

Compare Multiple Ranges and Return Non-Overlapping Sets

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related