StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If I understand the problem correctly, it is not an instance of the NP problem described in the paper you linked to. Here is my understanding of the problem, and a polynomial-time solution.</p> <ol> <li><p>We are given a finite set of ranges of real numbers, say n: [A1, B1], [A2, B2], ..., [An, Bn], where Ai <= Bi.</p></li> <li><p>Create a sorted list of the starting and ending points, ordered numerically, indicating whether the point is a starting or ending point. </p></li> </ol> <p>In your example, this would be: 12+, 14+, 15+, 17+, 20+, 21-, 22-, 25-, 27-, 62+, 64+, 65-, 70-, 80-</p> <ol> <li><p>Initialize curOverlap and maxOverlap to zero.</p></li> <li><p>Iterate through the list, incrementing curOverlap for each + and decrementing it for each -. Set maxOverlap = max(curOverlap, maxOverlap) on each increment.</p></li> </ol> <p>To continue your example:<br> val, cur, max<br> 12, 1, 1<br> 14, 2, 2<br> 15, 3, 3<br> 17, 4, 4<br> 20, 5, 5<br> 21, 4, 5<br> 22, 3, 5<br> 25, 2, 5<br> 27, 1, 5<br> 62, 2, 5<br> 64, 3, 5<br> 65, 2, 5<br> 70, 1, 5<br> 80, 0, 5 </p> <p>The max overlap is 5. You could also store the val associated with the max if you wanted to know where the max overlap occurred. That would give you 20. in this example. It's then trivial to go through the initial set of ranges and find the 5 which include 20.</p> <p>-edit- If you have repeated values, count the plusses before the minuses for each value so that you include ranges that overlap at a single point.</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