Loại trừ các khoảng thời gian chồng lên nhau

Question

Tôi có hai danh sách khoảng thời gian. Tôi muốn loại bỏ tất cả các lần từ list1 đã tồn tại trong list2. Ví dụ: List1:

[(0,10), (15,20)]

List2:

[(2,3), (5,6)]

Output:

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

Bất kỳ gợi ý nào?

Cố gắng để loại bỏ một khoảng thời gian vào thời điểm đó nhưng nó có vẻ như tôi cần phải thực hiện một cách tiếp cận khác nhau:

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

Tôi sẽ tiếp cận vấn đề này với thuật toán đường quét. Điểm bắt đầu và điểm kết thúc của các khoảng là các sự kiện, được đặt trong hàng đợi ưu tiên. Bạn chỉ cần di chuyển từ trái sang phải, dừng lại ở mọi sự kiện và cập nhật trạng thái hiện tại theo sự kiện đó.

tôi đã thực hiện nhỏ, trong đó tôi sử dụng như sau Interval lớp, chỉ vì đơn giản:

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 + ")"; 
    } 
} 

Những điểm sự kiện đề cập trước đó được đại diện bởi các lớp sau đây:

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

Bây giờ , những gì còn lại là xây dựng hàng đợi và thực hiện quét, như được hiển thị trong mã bên dưới

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; 
    } 
} 

Kết quả này bằng:

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

Answer 2

Bạn có thể muốn sử dụng một interval tree - điều này sẽ nhanh chóng cho bạn biết nếu một khoảng thời gian trùng lặp với bất kỳ khoảng thời gian trong cây.

Một khi bạn có một tập hợp các khoảng thời gian chồng chéo nhiệm vụ khá dễ dàng (interval1 là từ list1, interval2 là khoảng thời gian chồng chéo từ list2/cây khoảng): nếu interval1 chứa interval2, thì bạn có hai khoảng mới (interval1min , interval2min), (interval2max, interval1max); nếu interval1 không chứa interval2, thì bạn chỉ có một khoảng thời gian mới (interval1min, interval2min) hoặc (interval2max, interval1max)