StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POA range intersection algorithm better than O(n)?
text
Body
copied!<p>Range intersection is a simple, but non-trivial problem.</p> <p>Its has been answered twice already:</p> <ul> <li><a href="https://stackoverflow.com/questions/224878/find-number-range-intersection">Find number range intersection</a></li> <li><a href="https://stackoverflow.com/questions/143552/comparing-date-ranges">Comparing date ranges</a></li> </ul> <p>The first solutions is O(n) and the second solution is for a database (which is less than O(n) of course).</p> <p>I have the same problem, but for a large n and I am not within a database.</p> <p>This problem seems to be very similar to <a href="https://stackoverflow.com/questions/303243/store-2d-points-for-quick-retrieval-of-those-inside-a-rectangle">Store 2D points for quick retrieval of those inside a rectangle</a> but I don't see how it maps.</p> <p>So what data structure would you store the set of ranges in, such that a search on a range costs less than O(n)? (Extra credit for using libraries available for Java)</p> <p><b>EDIT:</b></p> <p>I want to get a subset of all intersecting ranges, meaning the search range could intersect multiple ranges. </p> <p>The method that needs to be less than O(n) in Java is:</p> <pre><code>public class RangeSet { .... public Set<Range> intersects(Range range); .... } </code></pre> <p>Where Range is just a class containing a pair of int start and end.</p> <p>This is not an impossible question, I already have the solution, I just wanted to see if there was a more standard/simpler way of doing it</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload