Databases
StackOverflow2013
Postsdbo
POEfficient algorithm for finding the largest overlapping range given a list of ranges
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POEfficient algorithm for finding the largest overlapping range given a list of ranges
    primarykey
    data
    text
    <p>Consider the following interface that describes a continuous range of <code>integer</code> values.</p> <pre class="lang-cs prettyprint-override"><code>public interface IRange { int Minimum { get;} int Maximum { get;} IRange LargestOverlapRange(IEnumerable&lt;IRange&gt; ranges); } </code></pre> <p>I am looking for an efficient algorithm to find the largest overlap range given a list of <code>IRange</code> objects. The idea is briefly outlined in the following diagram. Where the top numbers represent the <code>integer</code> values, and the <code>|-----|</code> represent the <code>IRange</code> objects with a min and max value. I stacked the <code>IRange</code> objects so that the solution is easy to visualize.</p> <pre><code>0123456789 ... N |-------| |------------| |-----| |---------| |---| |---| |------------| |--------| |---------------| |----------| </code></pre> <p>Here, the <code>LargestOverlapRange</code> method would return:</p> <pre><code> |---| </code></pre> <p>Since that range has a total of 4 'overlaps'. If there are two separate <code>IRange</code> with the same number of overlaps, I want to return <code>null</code>.</p> <p>Here is some brief code of what I tried.</p> <pre class="lang-cs prettyprint-override"><code>public class Range : IRange { public IRange LargestOverlapRange(IEnumerable&lt;IRange&gt; ranges) { int maxInt = 20000; // Create a histogram of the counts int[] histogram = new int[maxInt]; foreach(IRange range in ranges) { for(int i=range.Minimum; i &lt;= range.Maximum; i++) { histogram[i]++; } } // Find the mode of the histogram int mode = 0; int bin = 0; for(int i =0; i &lt; maxInt; i++) { if(histogram[i] &gt; mode) { mode = histogram[i]; bin = i; } } // Construct a new range of the mode values, if they are continuous Range range; for(int i = bin; i &lt; maxInt; i++) { if(histogram[i] == mode) { if(range != null) return null; // violates two ranges with the same mode range = new Range(); range.Minimum = i; while(i &lt; maxInt &amp;&amp; histrogram[i] == mode) i++; range.Maximum = i; } } return range; } } </code></pre> <p>This involves four loops and is easily O(n^2) if not higher. Is there a more efficient algorithm (speed wise) to find the largest overlap range from a list of other ranges?</p> <p><strong>EDIT</strong></p> <p>Yes, the O(n^2) is not correct, I was thinking about it incorrectly. It should be O(N * M) as was pointed out in the comments.</p> <p><strong>EDIT 2</strong></p> <p>Let me stipulate a few things, the absolute min and max values of the <code>integer</code> values will be from (0, 20000). Secondly, the average number of <code>IRange</code> will be on the order of 100. I don't know if this will change the way the algorithm is designed. </p> <p><strong>EDIT 3</strong></p> <p>I am implementing this algorithm on a scientific instrument (a mass spectrometer) in which the speed of the data processing is paramount to the quality of data (faster analysis time = more spectra collected in time T). The firmware language (proprietary) only has arrays[] and is not object orientated. I choose C# since I am decent at porting concepts between the two languages and thought that in the interest of the SO community, a good answer would have a wider audience. </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USColonel Panic
    1. USMoop
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POEfficient algorithm for finding the largest overlapping range given a list of ranges
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POEfficient algorithm for finding the largest overlapping range given a list of ranges
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POEfficient algorithm for finding the largest overlapping range given a list of ranges
      1. USHamlet Hakobyan
      1. VTFavorite
    1. COIIRC you can do this with a double loop of the type: `for(var i = 0; i < array.length; i++) for(var j = i + 1; j < array.Length; j++) max = Math.max(max, GetOverlap(array[i], array[j]));`
      singulars
      1. POEfficient algorithm for finding the largest overlapping range given a list of ranges
      1. USAlxandr
    2. COThis is not O(N^2); it is O(N * M) where N is the number of ranges and M is the maximum value in the domain. I cannot think of anything better myself, but some smart cookies have worked on algorithms like this for many decades. Do a web search.
      singulars
      1. POEfficient algorithm for finding the largest overlapping range given a list of ranges
      1. USPieter Geerkens
    3. COI don't understand what you mean by 'largest overlapping range'. Please could you give more examples? Say the ranges were 1 to 5, 2 to 6, 4 to 10 and 15 to 20.
      singulars
      1. POEfficient algorithm for finding the largest overlapping range given a list of ranges
      1. USColonel Panic
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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