Naitu
25-10-2007, 21:32
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!
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!