• 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 ...
  • Campbell Ritchie
  • Paul Clapham
  • Tim Cooke
  • Jeanne Boyarsky
  • Liutauras Vilda
  • Frank Carver
  • Henry Wong
  • Ron McLeod
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Al Hobbs
  • Piet Souris
  • Himai Minh

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

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 ?


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.
You would be much easier to understand if you took that bucket off of your head. And that goes for the tiny ad too!
the value of filler advertising in 2021
    Bookmark Topic Watch Topic
  • New Topic