Algoritmo di unione per intervalli di sovrapposizione

Question

Algoritmo di unione per intervalli di sovrapposizione

#1 da (3 voti)

1

Ho cercato un algoritmo efficiente per unire intervalli di sovrapposizione su una gamma dinamica di intervalli. Ad esempio, (ora di inizio, ora di fine) saggio,

[(1, 2), (4, 8), (3, 10)]

diventa

[(1, 2), (3, 10)]

dopo l'unione perché (4, 8) e (3, 10) sono sovrapposti. Sovrapposizione significa che ogni parte dei due intervalli condivide lo stesso momento.

So quando viene fornita una matrice completa l'operazione può essere eseguita con una pila dopo aver ordinato gli intervalli in ordine crescente di ora di inizio ( riferimento: geeksforgeeks ). Ma questo algoritmo è efficacemente applicabile solo quando l'array dato non è dinamico, ma sto cercando quale sarà efficiente per l'array dinamico. Ad esempio, gli intervalli di array verranno aggiornati e inseriti frequentemente e gli intervalli dovrebbero essere uniti su ciascuna operazione.

array algorithms merging dynamic-programming dynamic-linking

posta Sazzad Hissain Khan 20.06.2017 - 20:01

fonte

1 risposta

Leggi altre domande sui tag array algorithms merging dynamic-programming dynamic-linking

Differenza tra ambiente QUALIF, UAT, PREPROD e PROD? Come è possibile creare un elenco di attività da eseguire in modo sincrono sullo stesso thread?

score 3 · Answer 1

In cosa consiste la matrice dinamica?

Continuerete comunque a memorizzare i valori in ordine crescente ordinato. Quindi dovrebbe essere una ricerca binaria relativamente semplice per trovare gli intervalli più vicini (in base all'avvio), quindi è sufficiente controllare uno o due intervalli per determinare la sovrapposizione (poiché è possibile garantire che gli intervalli esistenti non sovrapposizione).

La sfida che potresti avere è che questo approccio non è minimamente atomico. È necessario bloccare la raccolta mentre si esegue l'unione, che potrebbe non soddisfare i requisiti di aggiornamento / inserimento frequenti. Ma mantenendo le cose in ordine, dovresti essere in grado di mantenere la complessità algoritmica verso il basso.