Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

overlap between ranges

by hifirock (Novice)
on Jun 10, 2009 at 10:01 UTC ( #770272=perlquestion: print w/replies, xml ) Need Help??

hifirock has asked for the wisdom of the Perl Monks concerning the following question:

Hi Monks,
How can we find the overlap between number ranges.
For example i have five number ranges
a) 1 .. 10
b) 11 .. 20
c) 15 .. 25
d) 21 .. 30
e) 25 .. 35
In the above example 'c' and 'e' overlaps with rest of the ranges. How can i find out the particular range is overlapping?
can anyone help me to sort out the problem?

Replies are listed 'Best First'.
Re: overlap between ranges
by Corion (Pope) on Jun 10, 2009 at 10:07 UTC

    I would assume that the usual definition of overlap applies - that two sets overlap if they contain at least one common element.

    You haven't described what you've tried so far, so I'm going to only outline some potential approaches. As this is not a program writing site, but a site for discussion and help with specific programming problems, you won't get a complete program from me.

    The naive approach:

    1. Generate all elements for the range
    2. Check for every two ranges whether they overlap by checking whether they contain common elements. See perlfaq4.

    The direct approach

    Note that two ranges overlap if

  • The lower bound of one range is between the lower and upper bound of the other range
  • The upper bound of one range is between the lower and upper bound of the other range
  1. For each range, check if they fulfill the modified criteria against each other range

There are other possibilities, like sorting your ranges by lower boundary and then checking for overlap - if you do it that way, you will need to add some more criteria for completely contained subranges.

Re: overlap between ranges
by JavaFan (Canon) on Jun 10, 2009 at 11:12 UTC
    Simple solution: take all the begin and end points of the ranges. Sort them. Loop over the resulting list. Any time you don't have the end point of range immediately following the begin point of the same range, you have overlap. How to deal with ranges sharing endpoints is left as an exercise to the reader.

    In your case, the resulting after sorting is (marking begin points with a capital letter, end points with a lowercase letter)

    1(A), 10(a), 11(B), 15(C), 20(b), 21(D), 25(c), 25(E), 30(d), 35(e).
    So, c overlaps b, d overlaps c, e overlaps d, and whether e overlaps c is something you'll have to further specify.
Re: overlap between ranges
by toolic (Bishop) on Jun 10, 2009 at 16:07 UTC
Re: overlap between ranges
by punch_card_don (Curate) on Jun 10, 2009 at 12:50 UTC
    ..In the above example 'c' and 'e' overlaps with rest of the ranges...

    Forgive my thickness, but I don't see how c or e overlap with a, nor how e overlaps with b. So I wonder if the problem has been expressed accurately.




    Time flies like an arrow. Fruit flies like a banana.
Re: overlap between ranges
by Anonymous Monk on Feb 19, 2014 at 09:42 UTC
    Thanks for solution provided great help.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://770272]
Approved by marto
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2019-12-10 04:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?