come unire efficacemente intervalli int in uno stream?

Question

Ci viene dato un flusso continuo di intervalli interi come [1,3], [5,10], [2,6], ... quando arriva ogni nuova gamma, dobbiamo controllare con intervalli esistenti e vedere se si sovrappone a qualsiasi intervallo esistente e, se viene rilevata una sovrapposizione, tutti gli intervalli sovrapposti vengono rimossi e viene invece inserito l'intervallo unito. Abbiamo bisogno di un algoritmo efficiente per questo. Si noti che l'intervallo viene fornito uno alla volta che forma uno stream ...

È stata posta questa domanda durante un'intervista. Idee?

L'intento è quello di unire intervalli sovrapposti in uno. per esempio, se abbiamo 3 gamme che vengono nel seguente ordine: [1,3], [2,6], [5,10]. Quindi prima fondiamo i primi due in [1,6], quindi ci fondiamo con il terzo e diventa [1,10].

Answer 1

Quando una nuova tupla entra in (newstart,newend), eseguire una ricerca binaria newstart-1 nell'elenco di elementi di chiusura esistenti e allo stesso modo per newend+1 nell'elenco di elementi di apertura esistenti.

Unisci con qualsiasi intervallo di corrispondenza.

Se nessun intervallo corrisponde, inserire tra i due campi più vicini.

Aggiornamento: Gratta che, stavo risolvendo il problema sbagliato: la fusione di intervalli di contatto. Ma la soluzione di sovrapposizione non sarà troppo dissimile.

1. di ricerca binaria per il più grande elemento di partenza esistente in cui start(n) <= newstart
2. di ricerca binaria per il più piccolo elemento che termina esistente in cui end(n) >= newstart
3. Se i due di ritorno lo stesso indice, il vostro inizio tupla è unificabile con l'ingresso n-esimo, sostituire newstart con start(n)
4. di ricerca binaria per il più grande elemento di partenza esistente in cui start(m) <= newend
5. di ricerca binaria per il più piccolo elemento di fine esistente in cui end(m) >= newend
6. Se i due tornano lo stesso indice, la vostra fine tupla è unificabile con l'entrata mese, sostituire newend con end(m)
7. sostituire tutte le voci tra l'indice ennesima e mese con il (newstart,newend) tupla.

Answer 2

È possibile rappresentare l'intervallo come una singola sequenza di punti "on" e "off" alternati. Ogni volta che arriva un nuovo intervallo, vengono cercati i suoi punti di inizio e fine e le azioni appropriate di fusione o inserimento.

Per ottenere buone prestazioni per le operazioni richieste — cercare, inserire ed eliminare — qui si potrebbe utilizzare qualcosa come un albero B qui.

Answer 3

L'algoritmo standard per questo problema è un interval tree.

Answer 4

Interval tree server lo scopo, ma ecco un altro approccio che ho usato per aggiungere alla gamma.

L'ipotesi è che l'elenco a cui viene aggiunta la nuova tupla (una rana) sia vuoto o non abbia intervalli sovrapposti.In secondo luogo, l'input è del formato a, b dove a < = b È possibile convertire l'elenco di tuple in un unico elenco di numeri e quindi aggiungere la nuova tupla ad esso.

Consentire a rangeList di essere l'attuale elenco di intervalli. per esempio. [1, 4, 6, 10, 12, 14] significherebbe un elenco gamma di [(1, 4), (6, 10), (12, 14)]

1. Se l'elenco è vuoto, semplicemente inserisci gli elementi della tupla nella lista ed hai finito
2. Trova la posizione dell'elemento a, b nella lista usando la ricerca binaria. (Se l'elemento non esiste, restituire la posizione dell'elemento minore maggiore del numero cercato)
3. Lasciate che le posizioni restituite siano pos_a, pos_b per gli elementi di tupla a, b rispettivamente.
4. Se pos_a è ancora, list_A = [a]
5. Se pos_b è ancora, list_B = [b]
6. Il nuovo elenco = rangeList [0: pos_a] + list_A + list_B + rangeList [b: end] e hai finito.

Convertendo l'elenco di tuple in una singola lista, eliminiamo la necessità di confrontare i nuovi elementi con 2 elenchi diversi. Quindi, trovando la sua posizione facilmente e controllando per dispari o pari, ci dice se si trova tra un intervallo esistente

def subroutine(rangeList, currTuple) 
""" 
rangeList: Existing list of non overlapping tuples 
currTuple: The range tuple to be added 
""" 
    if not rangeList: 
     rangeList.extend(currTuple) 
    else: 
     a, b = binSearch(currTuple, rangeList) 
     list_changed = rangeList[0:a] 
     if a%2 == 0: 
      list_changed.append(currTuple[0]) 
     if b%2 == 0: 
      list_changed.append(currTuple[1]) 
     list_changed.extend(rangeList[b:]) 
    return list_changed