title: Combining intersecting intervals
body: <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>