Odstęp czasu ustawiony w java

Question

Mam listę interwałów o wartościach całkowitych [np. [1, 4], [10, 19] itd.]. Czy istnieje sposób na umieszczenie tych odstępów w pojemnikach niektórych kolekcji java [np. Ustaw] tak, że mogę wywołać funkcję "zjednoczenia" na kontenerze. Funkcja "union" powinna dać mi listę interwałów, tak, że jeśli dwa wstawione interwały zachodzą na siebie, powinny zostać połączone w wynik. Próbowałem używać klasy Range w Guava, ale zakończyłem porównywanie wszystkich przedziałów przed połączeniem. Eleganckie podejście do tego byłoby naprawdę docenione! Oto, co wypróbowałem na podstawie odpowiedzi poniżej. Wynik jest [[1, 15], [17, 20]], który jest poprawny. Chciałem się dowiedzieć, czy istnieje jakiś interfejs API, który implementuje coś takiego.

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

dzięki

Answer 1

To jest dokładnie to, co RangeSet robi w wydanym właśnie Guava 14.0, z wyjątkiem tego, że łączy się z tobą, zamiast informować, które zakresy mogą zostać scalone.

Answer 2

podstawowego algorytmu:

1. Uporządkuj odstępach indeksu początkowego
2. przejść przez liście. Dla pozycji i th pozycja:
   1. Porównaj indeks końcowy i z indeksem początkowym pozycji (i+1) s.
   2. Jeśli indeks końcowy jest większy, ustaw indeks końcowy i na indeks końcowy i+1 i usuń element i+1. (To łączy je.)

złożoność czasowa: O(nlgn), ponieważ początkowego rodzaju. (To znaczy, jeśli usunięcie odbywa się prawidłowo.)