Databases
StackOverflow2013
Postsdbo
POCombining intersecting intervals
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCombining intersecting intervals
    primarykey
    data
    text
    <blockquote> <p><strong>Possible Duplicate:</strong><br> <a href="https://stackoverflow.com/questions/1034802/union-of-intervals">Union of intervals</a><br> <a href="https://stackoverflow.com/questions/5313374/how-to-overlap-intervals-efficiently">how to overlap intervals efficiently</a> </p> </blockquote> <p>Given a list of intervals say all integers, it should be possible to collapse them into one interval if they do intersect or overlap otherwise the given intervals remain unaffected. Say, if the input is e.g.I [(2-6), (1-4), (8-12)], the expected output is [(1-6), (8-12)] e.g. II [(4-7), (2-6), (1-4), (8-12), (7-9)] the expected output is [(1-12)].</p> <p>Correction: Missed the sorting part, so yes, it is a O(nlogn) time NOT O(n). Thanks for pointing that out. I have written and tested a O(nlogn) time and O(2n) space algorithm approach that works. Sharing the code of this approach below. I am interested in hearing different approaches to solving this problem, possibly more efficient.</p> <p>//Assuming each of the intervals, (2-6) and so on are represented as "Interval" objects (class definition shown below), where low = 2 and high = 6 // Step1: Sort by the low endpoint of the given intervals // Step2: find Union of the sorted intervals</p> <p>//Input:</p> <pre><code>List&lt;Interval&gt; intervalList = new ArrayList&lt;Interval&gt;(); </code></pre> <p>//Output:</p> <pre><code>List&lt;Interval&gt; unionList = new ArrayList&lt;Interval&gt;(); private static final Comparator&lt;Interval&gt; Low_EPSorter = new LowEPSorter(); class Interval { int low, high; Interval(int l, int h, int m) { low = l; high = h; } } </code></pre> <p>////-------BEGIN: Method which finds the Union Of given intervals ----//////</p> <pre><code>void UnionOfIntervals() { //Find intersection and combine intervals as necessary int sz = intervalList.size(); // sort by low endpoint Collections.sort(intervalList, Low_EPSorter); for(int i = 0; i &lt; sz; i++) { int j = i; if(j &gt; 0) { if( Intervals.intersect(intervalList.get(j), intervalList.get(j-1)) ) { Interval v = union(intervalList.get(j), intervalList.get(j-1)); checkAndAdd(v, unionList); } else { if(i == 1) { unionList.add(intervalList.get(j-1)); unionList.add(intervalList.get(j)); } else { unionList.add(intervalList.get(j)); } } //No intersection } //If 2 elements atleast } //Print intervals after union System.out.println("Input intervals after sorting:"); for(Interval v : intervalList) { System.out.print(v.low + "," + v.high + " "); } System.out.println(); System.out.println("Union of intervals:"); for(Interval v : unionList) { System.out.print(v.low + "," + v.high + " "); } } void checkAndAdd(Interval x, List t) { int top = t.size()-1; if( top &gt;=0 &amp;&amp; Intervals.intersect(unionList.get(top), x) ) { Interval v = union(unionList.get(top), x); t.remove(top); t.add(v); } else { t.add(x); } } </code></pre> <p>////-------END: Method which finds the Union Of given intervals ----//////</p> <p>////--- helper methods --- ////</p> <pre><code>static boolean intersect(Interval a, Interval b) { boolean r = false; if(b.high &lt; a.low || b.low &gt; a.high) r = false; else if(a.low &lt;= b.high &amp;&amp; b.low &lt;= a.high) r = true; return r; } Interval union(Interval a, Interval b) { int l = (a.low &lt; b.low) ? a.low : b.low; int max = (a.high &gt; b.high) ? a.high : b.high; return new Interval(l, max); } private static class LowEPSorter implements Comparator&lt;Interval&gt; { public int compare(Interval a, Interval b) { int r = 0; if(a.low &lt; b.low) r = -1; else if(a.low &gt; b.low) r = 1; return r; } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USsangv
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTDuplicate
    3. PL
      singulars
      1. LTLinked
    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
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POCombining intersecting intervals
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POCombining intersecting intervals
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POCombining intersecting intervals
      1. USuser448810
      1. VTFavorite
    1. COMy java experience is not the best, but your due to http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#sort(java.util.List, java.util.Comparator) you haven't written an algorithm that runs in O(n), but O(n * log n) instead
      singulars
      1. POCombining intersecting intervals
      1. UScitronas
    2. CO-1 for not researching and not paying attention to the suggested duplicates SO provided while entering this question. This has been answered multiple times on SO
      singulars
      1. POCombining intersecting intervals
      1. USJim Garrison
    3. COcan be solved in O(n) but highest number in the interval should be comparable to n.
      singulars
      1. POCombining intersecting intervals
      1. USAkashdeep Saluja
 

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