Intersezione di intervalli in tempo logaritmico

[Naitu]

Salve. Ho un problema da risolvere ma non riesco a farmi venire in mente una soluzione accettabile e,possibilmente, elegante.
Devo sviluppare un algoritmo che, dato un insieme di "n" intervalli di numeri interi (es. [1,2], [3,9] ...) e dato un intervallo "I", trovi tutti gli intervalli dell'insieme che intersecano con "I".

Condizioni:
1) Due intervalli adiacenti non si intersecano. Ad esempio [1,2] e [2,7] non si considerano intersecati
2) Se [x,y] è un intervallo, allora x > y, ovvero [z,z] non è un intervallo
3) Due intervalli di cui uno contiene completamente l'altro sono intersecati
4) La complessità della ricerca deve essere logaritmica sul numero di intervalli dell'insieme "n".

Ora, la rappresentazione di un intervallo si può fare con una coppia, o un record, o una struct del C o una classe Java. Insomma qualcosa del tipo:

class Range {
int begin;
int end;
}

La questione è scegliere una strategia di inserzione degli intervalli nell'insieme e/o di ordinamento e/o un'opportuna struttura dati per rappresentare l'insieme di intervalli in modo tale che la ricerca abbia logn come complessità.
Se qualcuno ha qualche idea mi salva + o + la vita :-)

Grazie!

[^TiGeRShArK^]

mmm..
così ad occhio direi che l'unico modo per risolvere il problema in maniera logaritmica è usare un albero di ricerca binaria...
però dovresti trovare il modo giusto di inserire gli intervalli nell'albero...
se ci pensi un pò (io ormai ho spento il cervello.. o quello che ne resta ) dovresti trovare la soluzione che ti permetta di risolvere il problema con una complessità logaritmica

[Naitu]

Già, anche io o pensato ad un albero. Il problema sta nel fatto che un intervallo può includere completamente un altro. Ad esempio, se ho [3-10] come radice, l'intervallo [1-4] lo metto a sinistra, [5-10] a destra, ma tipo [4-5] che è totalmente incluso in [3-10]? Idem per [2-20], che INCLUDE totalmente la radice.

Cmq grazie della risposta, almeno mi aiuta a consolidare i punti intermedi