重複間隔を除外する

Question

私は2つの間隔のリストを持っています。 list2に既に存在するlist1からすべての時間を削除したいと思います。 例： のList1：

[（0,10）、（15,20）]

LIST2：

[（2,3）、（5,6 ）]

出力：

[（0,2）、（3,5）、（6,10）、（15,20）]

任意のヒント？

は、一度に1つの間隔を削除しようとしましたが、私は別のアプローチを取る必要があるように思える：

public List<Interval> removeOneTime(Interval interval, Interval remove){ 
    List<Interval> removed = new LinkedList<Interval>(); 
    Interval overlap = interval.getOverlap(remove); 
    if(overlap.getLength() > 0){ 
     List<Interval> rms = interval.remove(overlap); 
     removed.addAll(rms); 
    } 
    return removed; 
} 

Answer 1

この問題はスイープラインアルゴリズムで解決します。インターバルの開始点と終了点はイベントで、優先度キューに入れられます。あなたは左から右に移動し、すべてのイベントで停止し、そのイベントに応じて現在のステータスを更新します。

私はちょうど簡単にするため、以下のIntervalクラスを使用した小型実装、作られた：前述のイベント・ポイントは、以下のクラスで表現されている

public class Interval { 
    public int start, end; 

    public Interval(int start, int end) {  
     this.start = start; 
     this.end = end; 
    } 

    public String toString() { 
     return "(" + start + "," + end + ")"; 
    } 
} 

を：

今

public class AnnotatedPoint implements Comparable<AnnotatedPoint> { 
    public int value; 
    public PointType type; 

    public AnnotatedPoint(int value, PointType type) { 
     this.value = value; 
     this.type = type; 
    } 

    @Override 
    public int compareTo(AnnotatedPoint other) { 
     if (other.value == this.value) { 
      return this.type.ordinal() < other.type.ordinal() ? -1 : 1; 
     } else { 
      return this.value < other.value ? -1 : 1; 
     } 
    } 

    // the order is important here: if multiple events happen at the same point, 
    // this is the order in which you want to deal with them 
    public enum PointType { 
     End, GapEnd, GapStart, Start 
    } 
} 

、残っているものは、以下のコードに示すように、キューを構築しスイープを行うことです。

public class Test { 

    public static void main(String[] args) {   
     List<Interval> interval = Arrays.asList(new Interval(0, 10), new Interval(15, 20)); 
     List<Interval> remove = Arrays.asList(new Interval(2, 3), new Interval(5, 6)); 

     List<AnnotatedPoint> queue = initQueue(interval, remove);  
     List<Interval> result = doSweep(queue); 

     // print result 
     for (Interval i : result) { 
      System.out.println(i); 
     } 
    } 

    private static List<AnnotatedPoint> initQueue(List<Interval> interval, List<Interval> remove) { 
     // annotate all points and put them in a list 
     List<AnnotatedPoint> queue = new ArrayList<>(); 
     for (Interval i : interval) { 
      queue.add(new AnnotatedPoint(i.start, PointType.Start)); 
      queue.add(new AnnotatedPoint(i.end, PointType.End)); 
     } 
     for (Interval i : remove) { 
      queue.add(new AnnotatedPoint(i.start, PointType.GapStart)); 
      queue.add(new AnnotatedPoint(i.end, PointType.GapEnd)); 
     } 

     // sort the queue 
     Collections.sort(queue); 

     return queue; 
    } 

    private static List<Interval> doSweep(List<AnnotatedPoint> queue) { 
     List<Interval> result = new ArrayList<>(); 

     // iterate over the queue  
     boolean isInterval = false; // isInterval: #Start seen > #End seen 
     boolean isGap = false;  // isGap:  #GapStart seen > #GapEnd seen 
     int intervalStart = 0; 
     for (AnnotatedPoint point : queue) { 
      switch (point.type) { 
      case Start: 
       if (!isGap) {     
        intervalStart = point.value; 
       } 
       isInterval = true; 
       break; 
      case End: 
       if (!isGap) {     
        result.add(new Interval(intervalStart, point.value)); 
       } 
       isInterval = false; 
       break; 
      case GapStart: 
       if (isInterval) {     
        result.add(new Interval(intervalStart, point.value)); 
       }    
       isGap = true; 
       break; 
      case GapEnd: 
       if (isInterval) { 
        intervalStart = point.value; 
       } 
       isGap = false; 
       break; 
      } 
     } 

     return result; 
    } 
} 

この結果は次のようになります。

(0,2) 
(3,5) 
(6,10) 
(15,20) 

Answer 2

おそらくinterval treeを使いたい - 間隔は任意のと重なっている場合、これはすぐに教えてくれます木の間隔の

オーバーラッピング間隔の設定が完了したら、タスクはかなり簡単になります（interval1はlist1から、interval2はlist2/intervalツリーからのオーバーラッピング間隔です）。interval1にinterval2が含まれている場合、 、interval2min）、（interval2max、interval1max）。 interval1にinterval2が含まれていない場合は、新しい間隔（interval1min、interval2min）または（interval2max、interval1max）が1つしかありません。