StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Call every interval (min,max)</p> <p>1) Sort your list of intervals by their <code>min</code>.</p> <p>2) Check to see if any <code>max</code> is greater than the next entry over's <code>min</code>. If they are, create the interval that is the smaller of their mins and the greater of their maxes, and add it back into the list in place of those two.</p> <p>3) Whenever you get a new interval, binary search into the list to add it, sorted by <code>min</code>. Then, using similar logic as in 2), attempt to merge it with the entry one below and one above until no more merges are possible.</p> <hr> <p>EDIT: A few changes.</p> <p>First, since we're using integers not floats, if you have an interval like 1,10 and 11,20 then there is no 'gap' between the 10 and 11 - so we should consider this to be one larger interval, 1,20. Reflect this by, instead of checking to see if <code>max > next min</code>, if <code>max >= next min - 1</code>.</p> <p>Second, if you want to find all intervals formed by overlap when merging a new interval into your list of intervals:</p> <p>1) Since your list of intervals is known to be in a state where it is sorted by <code>min</code> and also sorted by <code>max</code>, binary search into it to find the lowest min just above your new min and the highest max just above your new max.</p> <p>2) Iterate over min, max, min, max... etc in your array that are between your new min and new max. Below the lowest min, above the highest max and between each max/min you can compute the interval that is in the 'gap' there, and return them in e.g. an array.</p> <hr> <p>For example if your list of intervals contains 13,16, 21,24 and 31, 38 and you want to calculate the non-overlap of the new interval 1,30:</p> <p>1) We binary search into our list and find that 13 is the lowest min above 1 and 24 is the highest max above 30.</p> <p>2) We iterate like so:</p> <ul> <li>Between our min and the lowest min is 1 and 13 - so this forms an interval 1,12 (inclusive bottom, exclusive top). Add onto the return array.</li> <li>Between max and the next min is 16 and 21 - so this forms an interval 17,20 (exclusive on both ends). Add onto the return array.</li> <li>Between max and our max is 24 and 30 - so this forms an interval 25,30 (exclusive bottom, inclusive top). Add onto the return array.</li> </ul>

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