Intervall in Java eingestellt

Question

Ich habe eine Liste von Intervallen mit ganzzahligen Werten [z. [1, 4], [10, 19] usw.]. Gibt es eine Möglichkeit, diese Intervalle in einige Container von Java-Sammlungen zu legen [z. Setzen Sie] so, dass ich eine 'Union'-Funktion für den Container aufrufen kann. Die 'Union'-Funktion sollte mir eine Liste von Intervallen geben, so dass, wenn zwei eingefügte Intervalle sich überlappen, sie in der Ausgabe zusammengeführt werden sollten. Ich habe versucht, die Range-Klasse in Guava zu verwenden, aber habe alle Intervalle vor dem Zusammenführen verglichen. Ein eleganter Ansatz dazu wäre sehr geschätzt! Hier ist, was ich versucht habe, basierend auf der Antwort unten. Die Ausgabe ist [[1, 15], [17, 20]], was korrekt ist. Ich wollte wissen, ob es eine aufregende API gibt, die so etwas implementiert.

public static void main(String[] args) { 
    // mock data 
    List<MyIntRange> rng_lst = new ArrayList<Junk.MyIntRange>(); 
    rng_lst.add(new MyIntRange(1, 10)); 
    rng_lst.add(new MyIntRange(5, 15)); 
    rng_lst.add(new MyIntRange(17, 20)); 

    // sort intervals by start position 
    Collections.sort(rng_lst); 

    // merge the intervals which overlap 
    List<MyIntRange> res_lst = new ArrayList<Junk.MyIntRange>(); 
    MyIntRange old_rng = null; 
    for (MyIntRange cur_rng : rng_lst) { 
     if (old_rng == null) { 
      old_rng = cur_rng; 
     } else { 
      if (old_rng.rng.upperEndpoint() < cur_rng.rng.lowerEndpoint()) { 
       // this does not over lap with the next one 
       res_lst.add(old_rng); 
       old_rng = cur_rng; 
      } else { 
       // overlap 
       old_rng = new MyIntRange(old_rng.rng.lowerEndpoint(), 
         cur_rng.rng.upperEndpoint()); 
      } 
     } 
    } 
    // add the last range 
    res_lst.add(old_rng); 

    // done! 
    System.out.println(res_lst); 
} 

// wrapper around Guava's Range to make it comparable based on the 
// interval's start 
public static class MyIntRange implements Comparable<MyIntRange> { 
    Range<Integer> rng; 

    public MyIntRange(int start, int end) { 
     rng = Ranges.closed(start, end); 
    } 

    public int compareTo(MyIntRange that) { 
     int res = -1; 
     if (this.rng.lowerEndpoint() > that.rng.lowerEndpoint()) { 
      res = 1; 
     } 
     return res; 
    } 

    public String toString() { 
     return "[" + rng.lowerEndpoint() + ", " + rng.upperEndpoint() + "]"; 
    } 
} 

dank

Answer 1

Dies ist im Grunde genau das, was RangeSet in der gerade veröffentlichten Guava 14.0 tut, außer dass es das Zusammenführen für Sie tut, anstatt Ihnen zu sagen, welche Bereiche zusammengeführt werden könnten.

Answer 2

Ein grundlegenden Algorithmus:

1. Sortieren Intervalle von Startindex
2. Weg durch die Liste. Für den i Artikel:
   1. Vergleichen Sie den End-Index von i mit dem Startindex des (i+1) st item.
   2. Wenn der Endindex größer ist, setzen Sie den Endindex i auf den Endindex i+1, und entfernen Sie das Element i+1. (Dies fügt sie zusammen.)

Zeitkomplexität: O(nlgn), weil der Anfang sortieren. (Das heißt, wenn die Entfernungen richtig gemacht werden.)