java - Grouping objects based on overlapping time interval -

i have class,

class a{     ...     private interval interval;     ... }  //maintaining epoch time class interval{     private long left;     private long right;      public interval(long left, long right){         this.left = left;         this.right = right;     } //getters , setters } 

i have list of objects list<a> , want group objects have overlapping(transitive overlapping, i.e. a = b, b = c = c) intervals. lets suppose have 4 objects,

a1 - interval - 09:00 10:00 a2 - interval - 13:00 14:00 a3 - interval - 10:10 12:00 a4 - interval - 09:30 10:30 

the result of program should give me 2 lists,

list1 - a1,a3,a4 list2 - a2 

any suggestions on solving issue and/or pseudo-code?

sorry verbosity, believe question merits :-) . solution n*log(n) in number of intervals. location complexity occurs within sorting of intervals. note solution takes care include cases 1 interval contained inside another. result groups have sub-intervals reverse ordered, can fix if reversing list @ end. wouldn't recommend fixing inserting joined intervals @ beginning rather end increases complexity o(n^2) if using arraylist based implementation. suppose use linkedlist , insert @ beginning, might hurt in other places, depending on these groups after you've formed them.

public static long max(long a, long b){     return (a>b ? : b); }  public static long min(long a, long b){     return (a<b ? : b); }  /**  * meta interval composed of sub intervals. left endpoint  * leftmost point of subintervals , right endpoint   * rightmost point of subintervals.   */ static class metainterval extends interval{      /**      * meta intervals composed of lists of subintervals.      */     private list<interval> subintervals;      public metainterval(interval initialsubinterval){         super(initialsubinterval.getleft(),initialsubinterval.getright(),null);         this.subintervals = new arraylist<interval>();         this.subintervals.add(initialsubinterval);     }      public void join(metainterval other){         verifyoverlap(other);          this.setleft(min(this.getleft(),other.getleft()));         this.setright(max(this.getright(),other.getright()));         this.subintervals.addall(other.getsubintervals());          other.invalidate();     }      public void setsubintervals(list<interval> subintervals){         this.subintervals = subintervals;     }      public list<interval> getsubintervals(){         return this.subintervals;     }      private void invalidate(){         this.setsubintervals(null);         this.setleft(0);         this.setright(0);     }      public boolean isinvalid(){         return this.getsubintervals()==null;     }   }  //maintaining epoch time static class interval implements comparable<interval>{     private long left;     private long right;      private string intervalid;      public interval(long left, long right, string intervalid){         this.left = left;         this.right = right;         this.intervalid = intervalid;     }      public boolean pointisin(long point){         return (point>=this.getleft() && point<=this.getright());     }      public long getleft(){         return left;     }      public long getright(){         return right;     }      public void setleft(long left){         this.left = left;     }      public void setright(long right){         this.right = right;     }      public string getintervalid(){         return intervalid;     }      public boolean overlaps(interval other){         return pointisin(other.getleft()) || pointisin(other.getright()) || other.pointisin(getleft()) || other.pointisin(getright());     }      public void verifyoverlap(interval other){         if(!overlaps(other)){             throw new illegalstateexception("other interval not overlap");         }     }      /**      * sort leftmost part of interval.      */     @override     public int compareto(interval o) {         return long.compare(this.getleft(), o.getleft());     }      public string tostring(){         return intervalid+":["+getleft()+","+getright()+"]";     } }  /**  * given list of intervals, returns list of interval groups  * intervals in groups overlap. if overlaps b ,  * b c, a,b,and c returned in group. supposing intervals  * d  , e share nothing a, b, or c, share each other, d , e  * returned separate group a,b,c.  * @param baseintervals  * @return  */ public static list<list<interval>> getoverlappinggroups(list<interval> baseintervals){     list<metainterval> basemetaintervals = tometaintervals(baseintervals);      list<metainterval> mergedmetaintervals = getmergedmetaintervals(basemetaintervals);      list<list<interval>> intervalgroups = metaintervalstogroups(mergedmetaintervals);     return intervalgroups; }    private static list<metainterval> getmergedmetaintervals(         list<metainterval> metaintervals) {     if(metaintervals.isempty()){         return metaintervals;     }     //order meta intervals starting point.     collections.sort(metaintervals);      //go through , merge overlapping meta intervals.     //this relies on logic if interval overlaps     //an interval started before it, once intervals     //before have been merged, interval have starting point     //consecutive starting point of the preceeding interval.     for(int i=0; i< metaintervals.size()-1; i++){         metainterval thisinterval = metaintervals.get(i);         metainterval nextinterval = metaintervals.get(i+1);          if(thisinterval.overlaps(nextinterval)){             nextinterval.join(thisinterval);         }     }      list<metainterval> resultintervals = new arraylist<metainterval>();      //all intervals original list either:     //(a) didn't overlap others     //(b) overlapped others , chosen represent merged group or     //(c) overlapped others, represented in group in meta      // interval, , marked invalid.     //go through , add valid intervals returned.      for(metainterval : metaintervals){         if(!i.isinvalid()){             resultintervals.add(i);         }     }     return resultintervals; }  /**  * convert list of meta intervals groups of intervals.  * @param mergedmetaintervals  * @return  */ private static list<list<interval>> metaintervalstogroups(         list<metainterval> mergedmetaintervals) {     list<list<interval>> groups = new arraylist<>(mergedmetaintervals.size());     for(metainterval metainterval : mergedmetaintervals){         groups.add(metainterval.getsubintervals());     }     return groups; }  private static list<metainterval> tometaintervals(         list<interval> baseintervals) {     arraylist<metainterval> metaintervals = new arraylist<metainterval>(baseintervals.size());     for(interval : baseintervals){         metaintervals.add(new metainterval(i));     }      return metaintervals; }  public static void main(string[] args){     interval = new interval(20, 30, "a");     interval b = new interval(21,22,"b");     interval c = new interval(500,503,"c");     interval d = new interval(28,38, "d");     interval e = new interval(490,502,"e");        //note: a,b, , d overlapping group, ,     //d , e another.     list<list<interval>> intervalgroups = getoverlappinggroups(arrays.aslist(a,b,c,d,e));      for(list<interval> group : intervalgroups){         system.out.println(group.tostring());     } } 

output:

[d:[28,38], b:[21,22], a:[20,30]] [c:[500,503], e:[490,502]]