• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Intersecting Number Range Algorithm

 
Ranch Hand
Posts: 782
Python Chrome Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic