오버랩 간격 제외

Question

두 개의 간격 목록이 있습니다. List2에서 이미 존재하는 list1에서 모든 시간을 제거하고 싶습니다. 예 : 목록 1 :

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

목록 2 :

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

출력 :

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

어떤 힌트가 있습니까?

는 한 번에 하나의 간격을 제거하기 위해 시도하지만 난 다른 접근 방식을 취할 필요 것처럼 보인다 :

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

스윕 라인 알고리즘으로이 문제에 접근합니다. 간격의 시작 및 끝 지점은 이벤트이며 우선 순위 대기열에 놓입니다. 방금 왼쪽에서 오른쪽으로 이동하고 모든 이벤트를 중지하고 해당 이벤트에 따라 현재 상태를 업데이트합니다. 이제

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 Interval { 
    public int start, end; 

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

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

이벤트 포인트는 다음 클래스로 표현됩니다 :

난 그냥 간단하게하기 위해, 나는 Interval 클래스를 다음을 사용하는 작은 구현을 만든 , 아래 코드와 같이 큐를 만들고 스윕을 수행하는 것이 남아 있습니다.

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가 있으면 두 개의 새 간격이 있습니다 (interval1min , interval2min), (interval2max, interval1max); interval1에 interval2가 없으면 하나의 새 간격 (interval1min, interval2min) 또는 (interval2max, interval1max) 만 있습니다.