ओवरलैपिंग अंतराल को छोड़कर

Question

मेरे पास अंतराल की दो सूचियां हैं। मैं सूची 1 से हर बार हटाना चाहता हूं जो सूची 2 में पहले से मौजूद है। उदाहरण: List1:

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

List2:

[(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 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 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 चाहते हैं - यह जल्दी से आपको बता देंगे एक अंतराल किसी भी के साथ ओवरलैप हो अगर पेड़ में अंतराल के।

एक बार जब आप ओवरलैपिंग अंतराल का एक सेट रखते हैं तो कार्य काफी आसान होना चाहिए (अंतराल 1 सूची 1 से है, अंतराल 2 सूची 2/अंतराल पेड़ से ओवरलैपिंग अंतराल है): यदि अंतराल 1 में अंतराल 2 होता है, तो आपके पास दो नए अंतराल होते हैं (अंतराल 1min , interval2min), (अंतराल 2max, अंतराल 1max); यदि अंतराल 1 में अंतराल 2 नहीं है, तो आपके पास केवल एक नया अंतराल (अंतराल 1min, अंतराल 2min) या (अंतराल 2max, अंतराल 1max)