Viene fornita una serie di intervalli S. È necessario trovare tutti gli intervalli in S che sono contenuti in un dato intervallo (a, b) in una complessità temporale minima

Question

Viene fornita una serie di intervalli S. È necessario trovare tutti gli intervalli in S contenuti in un dato intervallo (a, b) con una complessità temporale minima.

Questo può essere fatto in O(n) tempo con la forza bruta, in cui n è il numero di intervalli in serie S. Ma se mi è permesso fare qualche pre-elaborazione, questo può essere fatto in meno di tempo O(n) ad es. O(log n) tempo?

Inizialmente pensavo interval tree, ma non credo che essa è applicabile qui perché albero intervallo viene utilizzata per ottenere tutti gli intervalli che si sovrappone con un dato intervallo.

Answer 1

È possibile rimodellare il problema sul piano 2D. Lascia che il (begin, end) di ogni intervallo sia un punto bidimensionale. (Si noti che tutti gli intervalli validi finiranno sopra la diagonale)

l'intervallo di-ricerca-problema si trasforma in gamma 2D ortogonale ben studiato query con algoritmi che hanno o runtime, dove k è il numero di punti segnalati.

Answer 2

Persistent binary search tree può essere utilizzato qui.

pre-processing:

1. Creare albero persistente vuoto. Dovrebbe memorizzare gli intervalli ordinati per i loro punti finali.
2. Ordinamento degli intervalli in base al loro punto di partenza.
3. Per ciascun intervallo, a partire dalla fine dell'elenco ordinato, creare una "copia" dell'albero persistente e aggiungere questo intervallo a questa copia.

Ricerca:

1. trovare il punto dell'intervallo query nella lista ordinata di partenza.
2. Iterare la "copia" corrispondente dell'albero persistente dalla chiave più piccola alla fine dell'intervallo della query.

La complessità del tempo di ricerca è O (log (n) + m), dove m è il numero di elementi nell'output.