Meaningless Drivel is fun!
The moose likes Beginning Java and the fly likes Intersecting Number Range Algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of Java Interview Guide this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Intersecting Number Range Algorithm" Watch "Intersecting Number Range Algorithm" New topic

Intersecting Number Range Algorithm

Pho Tek
Ranch Hand

Joined: Nov 05, 2000
Posts: 782


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 ?


David Harkness
Ranch Hand

Joined: Aug 07, 2003
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.
I agree. Here's the link:
subject: Intersecting Number Range Algorithm
It's not a secret anymore!