StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Just a quick thought 'off the cuff' so to speak.</p> <p>Could you organize them into 2 lists, one for start of intervals and the other for end of intervals.</p> <p>This way, you can compare y to the items in the start of interval list (say by binary search) to cut down the candidates based on that.</p> <p>You can then compare x to the items in the end of interval list.</p> <p><strong>EDIT</strong></p> <p><em>Case: Once Off</em></p> <p>If you are comparing only single interval to the list of intervals in a once-off situation, I don't believe sorting will help you out <a href="http://en.wikipedia.org/wiki/Sorting_algorithm" rel="nofollow">since ideal sorting is O(n)</a>.</p> <p>By doing a linear search through all x's to trim out any impossible intervals then doing another linear search through the remaining y's you can reduce your total work. While this is still O(n), without this you would be doing 2n comparisons, whereas on average, you would only do (3n-1)/2 comparisons this way.</p> <p>I believe this is the best you can do for an unsorted list.</p> <p><em>Case: Pre-sorting doesn't count</em></p> <p>In the case where you will be repeatedly comparing single intervals to this list of intervals and your pre-sort your list, you can achieve better results. The process above still applies, but by doing a binary search on the first list then the second you can get O(m log n) as opposed to O(mn), where m is the number of single intervals being compared. Note, still still gives you the advantage of reducing total comparisons. [2m log n compared to m(3(log n) - 1)/2]</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