Unisci intervalli a intervalli

Question

Dato un set di intervalli: {1-4, 6-7, 10-12} aggiungi un nuovo intervallo: (9,11) in modo che la soluzione finale sia 'unita': Output: {1 -4, 6-7, 9-12}. La fusione può avvenire su entrambi i lati (bassa e alta).

Ho visto questa domanda ha avuto risposta in più punti, qualcuno ha persino suggerito di usare Intervall Tress, ma non ha spiegato come esattamente lo userebbero. L'unica soluzione che conosco è di organizzare gli intervalli in ordine ascendente del loro orario di inizio e scorrere su di loro e cercando di unirli in modo appropriato.

Se qualcuno può aiutarmi a capire come possiamo usare gli alberi intervallati in questo caso d'uso, sarà fantastico!

[Ho seguito alberi intervallo in CLRS libro, ma non parlano la fusione, tutti parlano è l'inserimento e la ricerca.]

Answer 1

(sto supponendo che questo mezzo tali intervalli non possono mai sovrapporsi, poiché altrimenti verrebbero uniti.)

Un modo per fare questo sarebbe quello di memorizzare un albero di ricerca binario bilanciato con un nodo per endpoint di un intervallo. Ogni nodo sarebbe quindi contrassegnato come un nodo "aperto" che segna l'inizio di un intervallo o un nodo "vicino" che segna la fine di un intervallo.

Quando si inserisce una nuova gamma, si verificherà uno dei due casi rispetto al punto iniziale dell'intervallo:

1. È già all'interno di un intervallo, il che significa che si estenderà una gamma già esistente come parte l'inserimento.
2. Non è all'interno di un intervallo, quindi verrà creato un nuovo nodo "aperto".

Per determinare il caso in cui ci si trova, è possibile eseguire una ricerca predecessore nell'albero per il punto di inizio dell'intervallo. Se si ottiene NULL o un nodo chiuso, è necessario inserire un nuovo nodo aperto che rappresenta il punto iniziale dell'intervallo. Se ottieni un nodo aperto, continuerai semplicemente ad estendere tale intervallo.

Da lì, è necessario determinare quanto si estende l'intervallo. Per fare questo, calcolare continuamente il successore del nodo iniziale è stato inserito fino a quando si verifica una delle seguenti condizioni:

1. Hai guardato tutti i nodi dell'albero. In tal caso, è necessario inserire un nodo chiuso che segna la fine di questo intervallo.

2. Si vede un nodo chiuso dopo la fine dell'intervallo. In tal caso, ti trovi nel bel mezzo di un intervallo esistente al termine del nuovo intervallo, quindi non devi fare altro. Hai finito.

3. Si vede un nodo chiuso o aperto prima della fine dell'intervallo. In tal caso, è necessario rimuovere quel nodo dall'albero, poiché il vecchio intervallo è riassunto da quello nuovo.

4. Si vede un nodo aperto dopo la fine dell'intervallo. In tal caso, inserisci un nuovo nodo vicino nell'albero, poiché devi terminare l'intervallo corrente prima di vedere l'inizio di questo nuovo.

Implementato ingenuamente, il tempo di esecuzione di questo algoritmo è O (log n + k log n), dove n è il numero di intervalli e k è il numero di intervalli rimossi durante questo processo (dal momento che si deve fare n cancella). Tuttavia, è possibile accelerare fino a O (log n) utilizzando il seguente trucco. Poiché il processo di eliminazione elimina sempre nodi in una sequenza, è possibile utilizzare una ricerca successiva per l'endpoint per determinare la fine dell'intervallo da rimuovere. Quindi, è possibile unire il subrange per rimuovere dall'albero eseguendo due operazioni di divisione dell'albero e un'operazione di join di un albero. Su un albero bilanciato adatto (rosso-nero o splay, per esempio), questo può essere fatto in O (log n) tempo totale, che è molto più veloce se si vogliono includere molti intervalli.

Spero che questo aiuti!

Answer 2

check this out. Essa può aiutare: - http://www.boost.org/doc/libs/1_46_0/libs/icl/doc/html/index.html

La biblioteca offre queste funzionalità:

1) interval_set

2) separate_interval_set

3) split_interval_set

Answer 3

Questo viene fatto semplicemente aggiungendo l'intervallo in questione alla fine dell'intervallo impostato, quindi eseguendo un'unione su tutti gli elementi dell'intervallo impostato.

L'operazione di unione è ben dettagliato-qui: http://www.geeksforgeeks.org/merging-intervals/

Se non siete in vena di codice C++, ecco le stesse cose in pitone:

def mergeIntervals(self, intervalSet): 
    # interval set is an array. 
    # each interval is a dict w/ keys: startTime, endTime. 
    # algorithm from: http://www.geeksforgeeks.org/merging-intervals/ 
    import copy 
    intArray = copy.copy(intervalSet) 
    if len(intArray) <= 1: 
     return intArray 
    intArray.sort(key=lambda x: x.get('startTime')) 
    print "sorted array: %s" % (intArray) 
    myStack = [] #append and pop. 
    myStack.append(intArray[0]) 
    for i in range(1, len(intArray)): 
     top = myStack[0] 
     # if current interval NOT overlapping with stack top, push it on. 
     if (top['endTime'] < intArray[i]['startTime']): 
      myStack.append(intArray[i]) 
     # otherwise, if end of current is more, update top's endTime 
     elif (top['endTime'] < intArray[i]['endTime']): 
      top['endTime'] = intArray[i]['endTime'] 
      myStack.pop() 
      myStack.append(top) 

    print "merged array: %s" % (myStack) 
    return myStack 

non dimenticate la vostra nosetests per verificare che effettivamente fatto il diritto di lavoro:

class TestMyStuff(unittest.TestCase): 

    def test_mergeIntervals(self): 
     t = [ { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 11, 'endTime' : 15 }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46 } ] 
     mgs = MyClassWithMergeIntervalsMethod() 
     res = mgs.mergeIntervals(t) 
     assert res == [ { 'startTime' : 11, 'endTime' : 15 }, { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 44, 'endTime' : 46 }, { 'startTime' : 72, 'endTime' : 76 } ] 

     t = [ { 'startTime' : 33, 'endTime' : 36 }, { 'startTime' : 11, 'endTime' : 35 }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46 } ] 
     mgs = MyClassWithMergeIntervalsMethod() 
     res = mgs.mergeIntervals(t) 
     assert res == [{'endTime': 36, 'startTime': 11}, {'endTime': 46, 'startTime': 44}, {'endTime': 76, 'startTime': 72}] 

Answer 4

MergeIntervals classe pubblici {

public static class Interval { 

    public double start; 
    public double end; 

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

public static List<Interval> mergeInteval(List<Interval> nonOverlapInt, Interval another){ 

    List<Interval> merge = new ArrayList<>(); 

    for (Interval current : nonOverlapInt){ 

     if(current.end < another.start || another.end < current.start){ 
      merge.add(current); 
     } 
     else{ 

      another.start = current.start < another.start ? current.start : another.start ; 
      another.end = current.end < another.end ? another.end : current.end;     
     }   
    } 
    merge.add(another); 
    return merge; 
} 

Answer 5

C#

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

void AddInterval(List<Interval> list, Interval interval) 
{ 
    int lo = 0; 
    int hi = 0; 
    for (lo = 0; lo < list.Count; lo++) 
    { 
     if (interval.start < list[lo].start) 
     { 
      list.Insert(lo, interval); 
      hi++; 
      break; 
     } 
     if (interval.start >= list[lo].start && interval.start <= list[lo].end) 
     { 
      break; 
     } 
    } 
    if (lo == list.Count) 
    { 
     list.Add(interval); 
     return; 
    } 

    for (hi = hi + lo; hi < list.Count; hi++) 
    { 
     if (interval.end < list[hi].start) 
     { 
      hi--; 
      break; 
     } 
     if (interval.end >= list[hi].start && interval.end <= list[hi].end) 
     { 
      break; 
     } 
    } 
    if (hi == list.Count) 
    { 
     hi = list.Count - 1; 
    } 

    list[lo].start = Math.Min(interval.start, list[lo].start); 
    list[lo].end = Math.Max(interval.end, list[hi].end); 

    if (hi - lo > 0) 
    { 
     list.RemoveRange(lo + 1, hi - lo); 
    } 
}