Intervallo impostato in java

Question

Ho una lista di intervalli con valori interi [ad es. [1, 4], [10, 19] ecc.]. C'è un modo per inserire questi intervalli nel contenitore di alcune raccolte java [ad es. Impostato] in modo tale che possa chiamare una funzione 'unione' sul contenitore. La funzione 'union' dovrebbe darmi una lista di intervalli tale che se 2 intervalli inseriti si sovrappongono, allora dovrebbero essere uniti nell'output. Ho provato a utilizzare la classe Range in Guava ma ho finito per confrontare tutti gli intervalli uno con l'altro prima di unire. Un approccio elegante a questo sarebbe molto apprezzato! Ecco cosa ho provato in base alla risposta qui sotto. L'uscita è [[1, 15], [17, 20]], che è corretta. Volevo sapere se c'è qualche API in uscita che implementa qualcosa di simile.

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

grazie

Answer 1

Questo è fondamentalmente esattamente ciò che fa RangeSet nel Guava 14.0 appena rilasciato, tranne che fa la fusione per te, piuttosto che dirti quali intervalli potrebbero essere uniti.

Answer 2

Un algoritmo di base:

1. Ordina intervalli di indice di partenza
2. passeggiata attraverso la lista. Per lo i articolo:
   1. Confrontare l'indice finale di i con l'indice di inizio dell'articolo (i+1).
   2. Se l'indice finale è maggiore, impostare l'indice finale di i nell'indice finale di i+1 e rimuovere l'elemento i+1. (Questo li unisce.)

Tempo complessità: O(nlgn), a causa del tipo iniziale. (Cioè, se le rimozioni sono fatte bene.)