CODEWITHSUNDEEP
pythonpython-3.x
AnonPyDev
AnonPyDev

Reputation: 67

Compare Multiple Ranges and Return Non-Overlapping Sets

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.

Upvotes: 0

Views: 452

Answers (1)

Adrian Rutkowski
Adrian Rutkowski

Reputation: 309

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)))

Upvotes: 1

Related Questions