Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Intersecting Number Range Algorithm

Pho Tek
Ranch Hand
Posts: 782
Hi,

I have a programming problem which I want to share with you and hope you may have some ideas.

Problem statement

Define many number ranges in the form min->max,
where min, max are positive integers from 0 to 9999.
Implement a method such that given a list of number ranges, it will return true if non of the ranges intersect and false otherwise.

e.g. f ( 123..500, 499..700 ) returns true
f ( 123..500, 501..600, 601..800 ) returns false

Here is my current design.

One problem with this is that I need to create the individual numbers in the ranges as objects and throw them into the Set. So if the range is huge; then it becomes very memory intensive.

Any other ideas ?

Regards,

Pho

David Harkness
Ranch Hand
Posts: 1646
This will work and is a nifty solution, but you're correct that as the maximum range gets larger, this solution could suffer performance issues. Tricky as it is, even for small range cases it creates a lot of tempoerary objects that aren't necessary.

There are two other algorithms that come to mind immediately, one more brute-force than the other. The brute-force approach is to compare every range pair with the others and return false immediately if any intersect.

As a side note, this algorithm is O(n^2) -- "Oh n squared" -- in that it takes time relative to the number of inputs (n) squared because it involves n * (n - 1) / 2 ~ n^2 comparisons for n ranges. It's considered brute-force because it involves a staight-forward approach that doesn't take advantage of the extra information contained in the ranges.

If you create a Range class with a min and max field, it will be easier to manipulate them. You could add an Range.intersects(Range) method patterned after the Object.equals(Object) that returns true if two Ranges intersect. Another good one would be to override Object.compareTo(Object) to compare two Ranges so they can be ordered.

That's a hint to the smarter method. How would having the List of Ranges be ordered help you? Draw out some small examples with three ranges that cover the various possibilities of overlapping and non-overlapping ranges being ordered somehow.

If you get stuck on either of those or have other questions, don't hesitate to post the code you have so far and any compiler/runtime errors and questions. This is a cool assignment.