объектов Группировка на основе перекрытия интервала времени

Question

У меня есть класс,

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 and setters 
} 

У меня есть список объектов List<A>, и я хочу, чтобы сгруппировать объекты, которые имеют перекрывающиеся (переходные перекрытия, то есть a = b, b = c then a = c) интервалы. Давайте предположим, у меня есть 4 объекта,

A1 - Interval - 09:00 to 10:00 
A2 - Interval - 13:00 to 14:00 
A3 - Interval - 10:10 to 12:00 
A4 - Interval - 09:30 to 10:30 

Результатом программы должно дать мне 2 списка,

List1 - A1,A3,A4 
List2 - A2 

Любые предложения по решению этой проблемы и/или псевдо-код?

Answer 1

Извините за многословие, но я считаю, что вопрос заслуживает этого :-). Это решение равно n * log (n) в количестве интервалов. Место, где происходит эта сложность, заключается в сортировке интервалов. Обратите внимание, что в этом решении учитываются случаи, когда один интервал полностью содержится внутри другого. Группы результатов имеют свои подпериоды с обратным порядком, но вы можете легко исправить это, если хотите, изменив список в конце. Я бы не рекомендовал его исправлять, вставив объединенные интервалы в начале, а не в конец, поскольку это увеличивает сложность O (n^2), если вы используете реализацию на основе ArrayList. Я полагаю, вы могли бы использовать LinkedList и вставлять в начале, но это может повредить вам в других местах, в зависимости от того, что вы делаете с этими группами после того, как вы их создали.

public static long max(long a, long b){ 
    return (a>b ? a : b); 
} 

public static long min(long a, long b){ 
    return (a<b ? a : b); 
} 

/** 
* A meta interval is composed of sub intervals. Its left endpoint is 
* the leftmost point of its subintervals and its right endpoint is 
* the rightmost point of its subintervals. 
*/ 
static class MetaInterval extends Interval{ 

    /** 
    * meta intervals are 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 does not overlap"); 
     } 
    } 

    /** 
    * Sort by 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 a list of intervals, returns a list of interval groups where 
* the intervals in the groups all overlap. So if A overlaps with B and 
* B with C, then A,B,and C will be returned in a group. Supposing intervals 
* D and E share nothing with A, B, or C, but do share with each other, D and E 
* will be returned as a separate group from 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 the meta intervals by their starting point. 
    Collections.sort(metaIntervals); 

    //go through and merge the overlapping meta intervals. 
    //This relies on the logic that if interval i overlaps with 
    //an interval that started before it, then once all the intervals 
    //before i have been merged, interval i will have a starting point 
    //consecutive to the starting point of the 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 from the original list either: 
    //(a) didn't overlap with any others 
    //(b) overlapped with others and were chosen to represent the merged group or 
    //(c) overlapped with others, were represented in the group in another meta 
    // interval, and then marked as invalid. 
    //Go through and only add the valid intervals to be returned. 

    for(MetaInterval i : metaIntervals){ 
     if(!i.isInvalid()){ 
      resultIntervals.add(i); 
     } 
    } 
    return resultIntervals; 
} 

/** 
* Convert a list of meta intervals into 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 i : baseIntervals){ 
     metaIntervals.add(new MetaInterval(i)); 
    } 

    return metaIntervals; 
} 

public static void main(String[] args){ 
    Interval a = 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, and D are an overlapping group, and 
    //D and E are another. 
    List<List<Interval>> intervalGroups = getOverlappingGroups(Arrays.asList(a,b,c,d,e)); 

    for(List<Interval> group : intervalGroups){ 
     System.out.println(group.toString()); 
    } 
} 

Выход:

[D:[28,38], B:[21,22], A:[20,30]] 
[C:[500,503], E:[490,502]] 

Answer 2

Определить Interval класс (я не делал геттеры/сеттеры - я ленив, как это):

class Interval { 
    public long left; 
    public long right; 
    public String name; 
    public Interval(String name, long left, long right) { 
     this.name = name; 
     this.left = left; 
     this.right = right; 
    } 
    public boolean overlaps(Interval other) { 
     return (this.left >= other.left && this.left <= other.right) 
       || (this.right <= other.right && this.right >= other.left) 
       || (other.left >= this.left && other.left <= this.right) 
       || (other.right <= this.right && other.right >= this.left); 
    } 
} 

Теперь мы можем запустить этот программа:

public class Main { 
    public static void main(String[] args) { 
     ArrayList<Interval> all = new ArrayList<Interval>(); 
     all.add(new Interval("A",0,10)); 
     all.add(new Interval("B",30,40)); 
     all.add(new Interval("C",5,15)); 
     all.add(new Interval("D",15,30)); 

     // We run our algorithm... 
     ArrayList<ArrayList<Interval>> result = new ArrayList<ArrayList<Interval>>(); 
     for (Interval interval : all) { 
      if (result.isEmpty()) { 
       result.add(new ArrayList<Interval>()); 
       result.get(0).add(interval); 
      }else{ 
       boolean addedSomewhere = false; 
       for (ArrayList<Interval> group : result) { 
        for (Interval other : group) { 
         if (other.overlaps(interval)) { 
          group.add(interval); 
          addedSomewhere = true; 
         } 
         if (addedSomewhere) break; 
        } 
        if (addedSomewhere) break; 
       } 
       if (!addedSomewhere) { 
        result.add(new ArrayList<Interval>()); 
        result.get(result.size() - 1).add(interval); 
       } 
      } 
     } 

     // Print the result... 
     for (ArrayList<Interval> group : result) { 
      System.out.print("{"); 
      for (Interval interval : group) { 
       System.out.print("[" + interval.name + "," + interval.left + "," + interval.right + "]"); 
      } 
      System.out.print("}\n"); 
     } 
    } 
} 

, который выводит это:

{[A,0,10][C,5,15][D,15,30]} 
{[B,30,40]}